NP-overrated
gruhn.me
gruhn.me
2. When there's some large set of instances of some NP-hard problem that are tractably solvable in practice (like SAT), the importance of that is that there's some non-NP-hard subset here. Indeed, SAT is FPT (fixed parameter tractable [1]), an "easier" type of NP, for which decomposition can help. In contrast, graph colouring is thought to not be FPT.
You should stop thinking by analogy.
The article was showing the difference between mathematicians and engineers. For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions, whereas for engineers it's perfectly acceptable to eliminate some corner cases, thereby solving a reduced and simplified version of the general problem.
Except that's not really true, which is the whole point of the finer computational classes. If many instances are far from the worst case, that tells you something interesting about the class, which is why we have things like parameterised complexity. People who think that the theory is only interested in the general case of the broad classes you learn as an undergrad are just not sufficiently familiar with the theory.
There is a bunch of research devoted to Polynomial Time Approximation Schemes (PTAS). Mathematicians also take part in it.
No. Many engineers AND mathematicians worked for a long time to get us to a stage where Amazon can solve a billion SMT problems a day. To contribute, all of them had to understand the theory this article calls overrated.
2. That the worst-case is very hard usually tells you that many instances will be hard (unless you discover an easy subclass), as is the case here. And when many "natural" instances are easy, that means that the problem is more interesting than perhaps previously thought, and it requires and receives more research, not less. If most instances are near the worst case, it means you know all there is to know about the problem; when they're not, it means there's more to study.
But my favourite example (shown here in Java) demonstrates the difficulty of analysing simple, realistic programs without necessarily being undecidable:
long foo(long x) {
if (x <= 2 || (x & 1) != 0)
return 0;
for (var i = x; i > 0; i--)
if (bar(i) && bar(x - i))
return i;
throw new Error();
}
boolean bar(long x) {
for (var i = x - 1; i >= 2; i--)
for (var s = x; s >= 0; s -= i)
if (s == 0)
return false;
return true;
}
In fact that’s a big research thrust right now, to understand why many real-world SAT instances are solvable quickly while others are not, and where the threshold between them lies
Rather, if a problem is NP-complete/NP-hard it means that we cannot expect a general fast algorithms for exactly this problem (in other words: more mathematics is required, which mathematicians of course love).
But it is absolutely known that there exist other strategies:
- Develop algorithms that work well in practice and make understanding why they work so well in practice your career.
- Find out whether there exists something that makes the instances that occur in practice different from those instances that were used in the proof that the problem is NP-complete/-hard.
- For optimization problems: develop some fast algorithm which guarantees some approximation factor.
Isn't even just the question of minimising the length of a regular expression PSPACE-hard or so?
I don't get your point here. What analysis are you talking about?
I believe the claim usually made about non-turing-complete languages is that it is possible to prove specific properties with little to no calculations, that would be otherwise hard to calculate. For instance, the time needed to determine that an Idris program will eventually stop is litteraly 0 seconds.
Determining any kind of non-trivial property (i.e. a property that isn't true for all or none of the programs in the language).
> I believe the claim usually made about non-turing-complete languages is that it is possible to prove specific properties with little to no calculations, that would be otherwise hard to calculate. For instance, the time needed to determine that an Idris program will eventually stop is litteraly 0 seconds.
It's not the non-Turing-completeness that makes that practical. Let's take your example of Idris:
1. If a program's termination is hard to determine, then it will be hard to write it in Idris. I.e., the effort isn't gone, it's just shifted elsewhere. And if the program is easy to write in Idris, then its termination is also easy to prove in other languages (Idris effectively requires you to write a proof of termination, but you can write the proof for any language).
2. The importance of this is not as high as you think. For example, we can trivially rewrite all of the world's software in an always-terminating language (so not-Turing-complete), by changing the semantics of all programs to terminate after 2^100 steps. This will not affect the behaviour of any software, and you can see why it also won't make determining any of their properties of interest any easier.
So yes, Idris makes termination a trivial property for Idris programs, but it doesn't make the effort of determining whether an algorithm terminates or not easier (you just have to do it _while_ you're writing the program instead of after), and it doesn't, by itself, make any other property (which remains non-trivial) easier, such as "does the program terminate in fewer than 2^100 steps?"
That is the benefit of non-turing complete languages, though. Or, in general, the point of languages with useful type systems.
Writing the proof is not trivial, but languages like Rust or Idris make it simple because they force correctness early in the coding process.
That's simply untrue. You can write arbitrary proofs about programs in Turing-complete languages, too. In fact, most formal proofs are of programs written in Turing-complete languages.
> but languages like Rust or Idris make it simple because they force correctness early in the coding process.
Rust doesn't actually let you do that, though. In terms of the expressive power of proof, it is far closer to C than to Idris (in fact, from Idris's vantage point, Rust is almost indistinguishable from C).
> 2. When there's some large set of instances of some NP-hard problem that are tractably solvable in practice (like SAT), the importance of that is that there's some non-NP-hard subset here. Indeed, SAT is FPT (fixed parameter tractable [1]), an "easier" type of NP, for which decomposition can help. In contrast, graph colouring is thought to not be FPT.
Sorry but I need to clarify here. "SAT is FPT" does not mean anything. FPT only makes sense when you tell what is the *parameter*. Every problem is FPT when parametrized by the input size so graph colouring and SAT are FPT wrt to the size of the input (the graph and the formula respectively). What you meant: graph colouring parametrized by the number of colours is unlikely to be FPT (since it is W[1]-hard). SAT is FPT for many parameters such as treewidth (of the formula). Oh, and btw, graph colouring is also FPT when parametrized by treewidth (of the graph).
Now, I don't know if SAT being FPT (in a parameter of interest) has anything to do with the surprising ease of many "natural" instances (even with many variables), but my point was that when many instances are easy, that doesn't mean that the class is irrelevant, it just means it's more interesting (as there's obviously a tractable subclass, albeit one we haven't yet defined succinctly).
To first address the pedanticness: "FPT in the length of the input" is not excluded from the definition of FPT even if it is not an interesting case. Excluding these cases from the definition would make the theory uselessly complicated.
Now, back to the point of my first comment. It was mostly to show that you cannot use "FPTness" as an argument to justify that SAT is "easier" than graph colouring. I used "length of the input" to give an easy counter example, to show that FPT is not "an easier type of NP". It never has been. It is a way of understanding and measuring the complexity of the problem finely, to isolate hard parts of the input from the rest. What the W[1]-hardness of graph colouring parametrised by the number of colours tells you is that this parameter is not a relevant parameter and that's it. Graph colouring is FPT for many relevant graph parameters such as treewidth, clique-width (SAT is not even FPT wrt clique-width, but again, you cannot really use the concept of FPT to compare problems).
You will have a hard time using theory to justify that SAT is easier than any other NP-complete problem, because from the theory point of view, it is the hardest NP-problem you can get. Unless something unexpected happens in complexity theory, SAT cannot be efficiently solved in randomized time, SAT cannot be solved in sub-exponential time, SAT is complete under parsimonious reductions so you can basically take any NP-complete problem and build a CNF formula whose models are isomorphic to the solutions of the original instance etc.
The success of SAT solvers does not mean that SAT is easier than other NP-hard problem. It means that many combinatorial problems we need to solve in practice are "simple enough" that using the incredibly optimized smart way of bruteforcing the solution with a CDCL SAT solver is good enough. Now, take a cryptographic instance, translate it into a CNF formula and call a SAT solver, I doubt it will shine. Despite many attempts, this behaviour has never clearly be explained by the fact that the complexity of CDCL is FPT wrt a parameter that is small in industrial instances.
"Easier" perhaps isn't the right word (in terms of reducibility, it certainly isn't), but FPT is just a way to demonstrate that NP-complete problems can be different from each other in ways that matter (with respect to "natural" instances).
> Now, take a cryptographic instance, translate it into a CNF formula and call a SAT solver, I doubt it will shine.
Exactly. And researchers are very much interested in these differences that arise in natural instances and are hidden by "crude" reduction.
Not in a general sense, at least for standard complexity theory. It only deals with a very specific model of computation. Anyone with a sufficiently solid grasp of metamathematics intuitively understands that the distinction between solve and verify is nothing but a description of how badly matched our foundations are for the structure we're trying to view.
... This is the second time today I've posted about foundations like this.
What is an example of a model of computation where complexity theory doesn't apply?
Consider it like this, if the answer is in our system's axioms, we don't have to do anything. In a trivial sense that means we're just given the answer table, but it's also true if our substrate matches the model of computation its simulating. IE for an SLD-Resolution machine, running an SLD-Resolution object language, unification is worst case O(1). This is a degenerate case of course, but it's an example of something that's not realizable on a Turing machine's semantics where the worst case is in... EXPTIME? It's not great.
The more we treat our substrate like building blocks, and less like a holistic oracle, that changes our complexity landscape. Complexity theory was never about studying that whole landscape.
You might want to say CT is pragmatic and focused on realizable machines. There are two problems with that:
1. There's nothing special with the baseline used for complexity theory other than its familiarity. Reality is our ultimate substrate. The universe is not Turing tape. There is absolutely no serious basis upon which an argument against substrates can be made, especially with how little we know and understand about the universe.
2. Complexity theory isn't so pragmatic to only study the finitely bounded, which also changes everything. There seems a very tight upper bound on information in the universe. Even studying up to it as a limit is decidedly not pragmatic in the slightest. This is perfectly fine of course, the problem only enters in when we want to be "pragmatic" on some things, but not others.
I also want to clarify: There are higher orders of complexity theory that have generalized a lot of its concepts, even into hypercomputation which is cool, but then there's another problem I didn't mention. Complexity theory still isn't about what he said. It quantifies that distance between prove and verify, but it doesn't study the set of all those distances and how they arise. It just quantifies them one at a time and has only a limited number of things to say beyond that. What he described is simply mathematical logic.
I don’t think you can plausibly argue that complexity theory‘s base assumptions are a bad choice, at least not in the sense that you would assume that you can build exponentially more powerful computers in the physical universe. In fact, concerns about energy densities, limited amounts of matter, and the speed of light make it more difficult than typical machine models assume.
This is not true. Complexity theory very much looks at complexity under different models (alphabet size, oracles, circuits). It's just that often (e.g. in the case of alphabets), there is a reduction of known complexity between two models.
> It quantifies that distance between prove and verify, but it doesn't study the set of all those distances and how they arise.
This is also not true (https://en.wikipedia.org/wiki/Proof_complexity).
Every single time I've seen, for example, the lambda calculus be assigned cost semantics, it usually looks like what you would expect out of a Turing machine's simulation of it. Often times, they're explicit about it: https://www.sciencedirect.com/science/article/pii/S030439750...
For me, I can't accept that this is the criteria of "reasonable." Especially not for abstract theory.
I did try to indicate I'm mostly talking about standard complexity theory, the stuff you'd encounter on the surface level of the field. I'm not an expert in CT, but I do know enough to know what Landauer's principle is (and that it's been plausibly challenged.) I also know there's some crazy stuff in there, like descriptive complexity theory's link between Existential SOL and NP-Complexity.
> This is also not true (https://en.wikipedia.org/wiki/Proof_complexity).
Do you have any complexity theory papers that deal with this specifically? I've only ever seen that kind of work done in mathematical logic. Genuine interest in reading the CT approach.
You could assign it any cost model you want. Often this doesn't make a difference (as speedup theorems and other "distracting details" mean that most classes are intended to be separated by exponentials), but it is true that people are typically more interested in cost models that are more relevant to the physical universe (although number of reductions is very much the cost of focus in proof complexity). Indeed, relevant discoveries in physics yield corresponding computational complexity research, as in the case of quantum complexity (https://en.wikipedia.org/wiki/Quantum_complexity_theory).
> Do you have any complexity theory papers that deal with this specifically?
A Google Scholar search for "proof complexity" will show you many papers as well as a number of books.
That being said, a counterargument to press against this is that complexity theory doesn't restrict itself to physical or hypothetical physicality in its totality. As I mentioned, there are swaths of complexity theory work which bound quite far afield. The higher orders of the field are decidedly not-physical at all (and pedantically, hypercomputation isn't strictly computation). Of course even beyond this, we're still not studying the nature of computation, we're studying the cost. While you might say that of course these things are tied thanks to physicality (I wouldn't agree that they're equivalent on this basis, but I don't think that's an interesting semantic argument), I did also mention Landauer's principle being plausibly challenged, which is further problematic for conflating the two. Computation being reversible where entropy isn't doesn't explode complexity theory, but it does drive a wedge between information in a computer-sense and information in a thermodynamics sense. At that point, we don't have the claim in the first place, it's just a false friend. Something to consider.
> we're still not studying the nature of computation, we're studying the cost
That is one way of studying the nature of things, sort of like the use of the Hamiltonian in physics, especially if you're interested in problems and classes of problems, and their broad similarities and differences via reductions, rather than in specific computations.
> The higher orders of the field are decidedly not-physical at all (and pedantically, hypercomputation isn't strictly computation).
Hypercomputation isn't really a big part of the main thrust of complexity theory, but (computable) oracles do very much play an important role in complexity theory, even in its lowest complexity classes, such as in the relativisation barrier, which shows that some proof techniques cannot separate P from NP.
> I did also mention Landauer's principle being plausibly challenged,
That's not complexity theory, at least not the standard theory, which treats time and space (or circuit size) more abstractly than concrete physics. There are, however, theoretical reversible models, just note that they don't yield different "classic" deterministic complexity classes (i.e. they do not yield exponential differences).
> Hypercomputation isn't really a big part of the main thrust of complexity theory
I don't mean to imply that it was, though the results are actually relatively important elsewhere.
> That's not complexity theory, at least not the standard theory, which treats time and space (or circuit size) more abstractly than concrete physics.
More, but not totally abstractly. Steps and cells being vacuous primitives, they're not literally space-time, but within orthodoxy there's absolutely a partial morphism that's implied. That's why they're named like that. You are supposed to have them live close together in your head.
>There are, however, theoretical reversible models, just note that they don't yield different "classic" complexity classes
I know that some don't, but for example quantum models to use your own example, while not technically reversible in the absolute sense, do possess some reversibility capability and do derive different complexity classes.
I think it's very obvious that there should be reversible computational models which yield different complexity classes from the typical ones. To me for a field to qualify as a study on the nature of computation, it should probably be able to design one totally a posteriori, if in a higher order language. Complexity theory might be invoked in such a construction, but it's not the one doing the building. It's one of many in an orchestra.
Here's a question I have, since you do seem pretty well versed on CT. Universal quantification over complexity classes of first-order systems, used anywhere in the abstract?
I'm not sure what you mean by "complexity classes of first-order systems" and by "in the abstract".
But it seems like you're asking about the intersection of computational complexity and formal systems, and there's definitely work there. I already mentioned proof complexity, which analyses the number of deduction steps needed to prove something in various formalisms, and there are famous undergrad-level examples, such as TQBF (https://en.wikipedia.org/wiki/True_quantified_Boolean_formul...). But an intersection that is of more interest to me, as I'm interested in software correctness, is that of the model-checking problem.
Now, many people are confused whenever the model checking problem is discussed, because they confuse it with model checkers, which are a set of algorithms intended to solve the problem, but complexity theory is typically interested in the inherent difficulty of answering problems regardless of the algorithm used to do it. So the model checking problem is that of determining whether a formula in some formalism implies another formula, and its inherent complexity exists regardless of whether this question is answered via a formal proof or by some technique involving the logic's semantics. In the context of software verification, the model checking problem is that of determining - by whatever means - whether a program satisfies some non-trivial property.
Philippe Schnoebelen has some papers on the model checking problem in temporal logic (https://lsv.ens-paris-saclay.fr/Publis/PAPERS/PDF/Sch-aiml02..., https://lsv.ens-paris-saclay.fr/Publis/PAPERS/PDF/DLS-jcss-p...). One of his findings that I've found most interesting with regards to programming is that programming languages cannot, in general, make answering the question of whether a program satisfies some property any easier. This result is surprising. The reason is that without a programming language, we could describe a program as a huge state transition graph (this is called a Kripke structure). In that representation, it's been proven that verification is linear in the number of states, i.e. there is no general approach that is faster than brute-force. Now, the size relationship between a program written in a programming language and its Kripke structure is easily exponential or more, so if there were no algorithm that's better, in the worst case, than a brute force of the Kripke structure, then obviously verification is intractable in the size of the program. However, the number of Kripke structures of size N that have a succinct representation in some programming language is far smaller than the total number of Kripke structures of size N. So it could have been the case that analysing programs would have been easier than analysing their Kripke structure (while ignoring their representation in the language). But Schnoebelen proved that this is not the case.
He also proves that program decomposition (and verification of each component separately) cannot, in general, make verification any easier (i.e. the model checking problem isn't FPT in the number of program components).
These results are far more recent than the hopes expressed in the seventies and eighties that we'll be able to prove the correctness of all/most/many programs we write, and indeed, even though the results talk about the worst case, what we've seen in the last few decades is that the power of program verification indeed behaves more like the worst case than something far from it. The gap between the size of programs we can verify and the average size of programs we write has only widened (what saved the day has been the effectiveness of unsound methods, but that's a whole other discussion).
Don't allow the hard ones
Dependency managers tend to just block a huge category of situations that effectively eliminate the entire NP hard space
Type systems similarly are explicitly cordoned off
The trick isn't "do it anyway" beyond you kind of definitionly need to, it is to acknowledge the general problem is "impossible" so either do your best or start eliminating the impossible
For dependency resolution specifically, the set of possible dependencies is probably in the range 100 - 10000 for all ecosystems, even if the number of available packages in an ecosystem continues to grow.
Wait until you meet pip and liberal requirements.txt
> Don't encounter the hard ones
For example, with the simplex method for linear programming, we don't do anything about disallowing the hard instances. We just solve the problems as they come in and none of the ones we get asked to solve ever turn out to be hard. (Generalizing, of course.)
Can you elaborate on this? Many _try_ to get around this, e.g. Cargo's https://doc.rust-lang.org/cargo/reference/resolver.html#semv..., but it's not quite in P. Nix offloads dependency resolution to *2nix tools. Go's minimum version selection is just a tree walk, but it loses a fair amount of expressivity.
Not sure why more ecosystems don't do this. Sure an update could break dependents, but, like, you already have a big problem if a dependent was keeping you on an old version no matter what.
Building a SAT solver into the package manager seems to be a solution in search of a problem.
This is essentially Go's MVS. (Can only specify a minimum bound, can't depend across major version bumps). Any others? MVS is more the exception than the rule.
> Not sure why more ecosystems don't do this. Sure an update could break dependents, but, like, you already have a big problem if a dependent was keeping you on an old version no matter what.
I'll bite :-) You lose a lot of expressivity. Incompatibility is specified from the dependee, despite being a property of the dependency. I can point to instances where this has causes issues; e.g. dependees using unstable APIs. That's exactly why MVS uses the _minimum_ bound, to minimise such breaks.
> Building a SAT solver into the package manager seems to be a solution in search of a problem.
I agree in that there are better algorithms for error reporting! But NP-hardness is a pretty fundamental property of dependency resolution and removing it moves the pain somewhere else.
I can't tell you which ones off the top of my head, but I'm sure a number of package managers do use constraint solvers to find dependencies matching the constraints.
My understanding was NP is when you test and rebuild the graph over and over which doesn't need to happen if you isolate or fail
Not quite, Cargo only allows multiple versions of a package when they are semver incompatible (i.e. have different major versions).
If you allow multiple versions of a package you get some quite gnarly errors if you try to share values between them. The rationale of allowing semver incompatible versions is that they should be incompatible anyway.
Cargo has an interesting proposal on private and public dependencies that allows you to say multiple versions are only allowed when they aren't visible from the same part of the dependency graph https://rust-lang.github.io/rfcs/3516-public-private-depende...
There's probably a quantification of this in some sense for specific classes of NP-hard problems.
What's interesting is that many algorithms (especially in cryptography) are explicitly designed to create those combinatorial edge cases. A SAT solver looking at normal problems that occur in life and programming will do an amazing job. A SAT solver looking at SHA256, not so much. In fact, arguable the science of developing cryptographic systems is the science of finding these exponential explosions that are resistant to heuristic approximations.
Discussed here: https://cstheory.stackexchange.com/questions/33550
NP-hard problems are hard to solve exactly, but it's usually possible to get a pretty good approximate solution efficiently. But some search problems are just very hard, even approximately. If you've held an old Debian install through major upgrades with aptitude, you'll have had to see it get lost deep in outer search space pretty regularly.
Sometimes aptitude needs to downgrade a package, uninstall a package, or not install a recommended package to arrive at the right solution. There are many possible packages it could try to downgrade, and each of these creates a brand new mess with new possibilities. This is not something you get with other package managers, and its search strategy is genuinely intractable if you don't help it along by trying to manually figure out the small set of packages that create all the difficulty.
Another insight: I regularly find that clever O(logn) solutions are just obliterated by a few mostly-branch-free O(N) pre-passes followed by a problem that computers enjoy, like contiguous memory access and vector operations.
Use the royal "we" with caution, please.
P.S. in case it wasn't obvious, this isn't one of those "nyeh nyeh well you must be dumb because you don't cogitate in ways reminiscent of modern computing hardware" comments so much as a "you would not believe how simple-as-in-basic-as-in-limited some of us really cogitate while leveraging external systems to suggest otherwise ".
The Roc and Zig folks probably have actual numbers.
But nobody expects that. Hashmap is supposed to be faster once you have, like, ten elements. That's what was promised to us.
Benchmarked an order of magnitude faster than linear scan or binary search. I agree with your general sentiment tho, which is why I measured
There are probably even faster ways I don't know of.
You took away the wrong thing. The theory tells you that no good algorithm exists for _all_ possible inputs. This means you have to try to limit yourself to a subset of the problem space, and use heuristics to move all the remaining pathological cases (if any) to a corner you then monitor and ensure doesn't occur in practice too often.
Package managers are designed the way they are _because_ of the inherent NP-hardness, not _despite_ it as this article conveys.
In the formal models of dependency resolution, the three core conditions are: 1) Root package is included, 2) Dependency closure (everything required is present) 3) Version uniqueness (at most one version per package name)
NPM, yarn etc drop 3) which makes it not NP hard.
Go limits itself to minimum version selection which admits a linear time solution.
Cargo allows multiple major versions, thus reducing most cases of 3), and then relies on heuristics to prune and reduce the pathological cases to be relatively rare. There have been cases of real world trees that had issues, but then you add a heuristic that catches that type, and then eventually it becomes super rare. This style of design is adopted because of the known NP-hardness. We don't go around looking for algorithms to solve the general case, and we simplify the problem where possible knowing the benefit we get in return, or we watch and shift around the pathological cases to a rare corner, all because of knowing it is NP hard.
Amazon's SMT solvers and similar all use in principle similar tricks - only passing simplified encodings, portfolio solving i.e Promise.any(multiple solvers with same problem), timeouts + fallback, etc.
Another common example is the MIPs used by food delivery and other gig platform companies where the complexity of the solver is intentionally and aggressively slashed using as many tricks as possible.
A minor point, but npm peer dependencies mean that in theory it actually is NP-hard! Even if it's rarely exhibited in practice.
I'm curious, which formal models of package management are you referencing?
I'm more willing to believe they were taught the wrong thing.
Author used a rhetorical device that you seem to have missed.
The opening premise is: NP-hardness is easy in theory, hard in practice, the point made is that it’s easy in practice. But that premise is itself wrong: complexity theorists know that NP-hardness is in fact, hard in theory.
Sales people still have to plan their trips even though finding the optimal solution is NP-hard (to give one example). No matter; there are decent heuristic methods.
* Do not implement an np solution trying to get the perfect score. Implement a fast solution that gets within x% of optimal
* If a solution seems impossible or it takes too long, return the closes solution you can find, and a warning about the solution being suboptimal
I got the code in a few minutes. On a sample of random inputs, the algorithm produces a solution within 1% of optimal in ~99.9% of the cases. p95 execution time is well below 2ms in my laptop.
That's it, that's everything you need for a production system. "close enough" very fast is sufficient, and the impossible cases very rarely happen. Even when they do, you can simply work around them.
Luckily, there are pretty good heuristic solutions that work well in practice.
> Type checking (not all type systems)
> I mean, installing packages and type checking can surely be slow. But, at least in my career, I've never seen a galactic blow-up.
Swift was infamous of having exponential time type inference that made expressions like `"foo" + "bar" + "baz" + "qux" + 123` take literal minutes to fail with a compiler error.
Last time I had a galactic blow-up of apt solver (the final part of 64-bit time transition in Debian Testing) it was mere 2 GiB of memory per minute.
Debian allow you to choose different solver (typical Debian). It is easy to get galactic blow up if you insist.
For example, the minimum set cover problem shows up in cases like "What minimal set of test vectors covers all the conditions in my code?". There is an obvious greedy algorithm: "Start with nothing, pick the vector that covers the most yet-uncovered cases, repeat until all are covered".
There is an approximation result that says no polynomial time algorithm can do more than a small factor better than this greedy algorithm.
But this is a _worst case_ result, and absolutely useless for any problem you will encounter in practice.
It's trivial to come up with ways of improving the greedy algorithm: First off the simple greedy algorithm will often produce output which has completely redundant elements that can just be removed, because some collection of later added items that were necessary to cover some rare cases completely cover some earlier added item. Adding a simple postprocess to remove redundant elements immediately improves the greedy solution, particularly when the frequency of elements follows something power-law ish.
You can measure the frequency of each element and weigh uncovered elements by how rare they are (E.g. using entropy). This avoids the primary cause of the above duplicate selections.
You can use lookahead e.g. pick the pair of elements that together improve the score the most but then only commit to one.
You can use rarity weighed random starts, complete using whatever search you have, then retry multiple times.
You can compute new solutions using only the results of prior attempts. etc. etc.
In my experience basically any improvement over the greedy algorithm works on real problems, even before getting to a proper ILP solver. The greedy algorithm is just pathetic and will result in solutions much worse than you get from simple elaborations.
But over and over again you can find people being told to use the greedy algorithm because no polynomial time algorithm is better -- even in instances that are small and where actually enumerating all solutions might be tractable and justified.
We do have a polynomial algorithm for linear programming yet simplex (with exponential worst case performance) is our tool of choice.
I think the Ford-Fulkerson maximum flow algorithm may be another example.
Hehe, clearly the author hasn't written any SwiftUI.
Calculating general equilibrium over non divisible goods is NP hard. It is practically infeasible because your problem size is eight billion people each choosing from hundreds of millions of products to produce or consume.
Another problem is basically any form of non convex optimization because even the approximations require describing a non convex polygon as piecewise linear segments and therefore even the approximation algorithm are NP hard.
Now you will probably be like "what's the big deal? Just solve it like any other NP hard problem, with brute force. You only need to solve it once to prove that it is solvable."
Unfortunately this theoretical ability to solve a problem is useless in practice, because you need to solve the problem frequently. Let's say a thousand times per second. Yes, you only have a millisecond to solve the problem and you must produce an answer within that deadline.
In practice everyone has given up and uses QP approximations instead, disproving the premise of the article. You are better off with memorization based systems that classify the situation and then choose a memorized answer, like neural networks, and only after that do you actually try to use the QP solver to refine the solution. So yeah, if you build a machine like that you're throwing your hands up a thousand times per second saying "can't be done".
I'm still going to look for a more efficient way to do it, but sometimes you can go a long way without scaling. Not everything needs to scale to large numbers.
A lot of simulation we only have exponential-time algorithms for. Motion planning, protein folding, etc. For a lot of these today, the SOTA is to use an NN model to learn the heuristics from data. OP's claim only rings true if one can only think of just the algorithms that undergrad CS now studies.
(Note: I'm speaking vaguley, on the same vague level as your comment. I can be more precise as to what my indications indicate)
>>> And now you've learned that almost all interesting problems are undecidable and of the remaining ones, almost all are NP-hard. For the project of computer science, that puts the final nail in the coffin.
> Sheesh. Not sure if everyone got such a dire framing but that would explain.
Honestly, this is what makes computer science fun.
In normal situations, it is not a problem, I have written thousands of regex without ever hitting a galactic case (at least not one I am aware of).
But it can still be a problem because if the regex engine is too powerful and accepts user input, a specially crafted regex can be used as a denial of service attack.
Oh you think you'll never write a regex like that? Think again. It took down all of Cloudflare once: https://blog.cloudflare.com/details-of-the-cloudflare-outage...
Much simpler in these cases to use a regex engine with runtime guarantees. It may not support some advanced features, but you are sure that it won't explode.
Whether you chose to use a regex engine with runtime guarantees or one that support NP-hard features depends on the situation. If you are in control, it is not worth limiting yourself for the rare case it might explode, just Ctrl-C if it happens and move on. But on an automated system that deals with user data, you want the guarantees.
That's a good idea.
If you have to use one that supports NP-hard features I think a configurable CPU time timeout is also a reasonable backstop, just as configurable timeouts are reasonable in network code.
> Everyone knows you can tackle those with heuristics, but you don't have to sacrifice optimality.
Unless you're using some weird definition of optimality, or happen to have a proof of N=NP in your back pocket: yes, yes you do.
You don't have to sacrifice "good enough". You don't have to let it run for an insane amount of time. Just about all interesting problems that I know of have either (1) good heuristics that in practice get close enough to optimal that nobody needs to care about the gap, or (2) constraints or restrictions that are totally fine to apply in practice.
But those are both ways of sacrificing optimality. You have to sacrifice optimality. It just turns out that optimality isn't usually very important, especially when 99% of optimality is achievable.
> We absolutely have tools that can find provably optimal solutions in reasonable time. There's no magic. No quantum computers. Just thinking harder and coming up with better algorithms.
No, we absolutely do not. Again, not unless someone has secretly come up with a constructive proof of P=NP. "Optimality" in the first sentence, "provably optimal" here, those terms are precise -- so I'm confused why the author is claiming that multiple people have achieved the impossible.
The article clears up one serious confusion only to replace it with another?
> Everyone knows you can tackle those with heuristics, but you don't (ALWAYS) have to sacrifice optimality
> We absolutely have tools that can (OFTEN) find provably optimal solutions in reasonable time
Well, not really. Massive chunks of the search space can be eliminated through clever (but non-optimal) algorithms. The rest of the search space can usually be explored through heuristics. In practice, we can solve gigantic TSP problems "well enough" and "fast enough".
It reminds me of the Midwit meme. Both the low IQ and high IQ folks say "Heuristics are good enough". Only the mid IQ guy cares about NP-hard.
That's not to take away from the research into theoretical limits of computation. Just noting that's a completely different question from the practical concerns of actually solving those problems IRL
Another interesting NP-complete problem is minesweeper and closer to true since minesweeper problems can have variable size by their definition.
What is the "n that goes to infinity" for Sudoku? I thought that you could iterate through all possible 9x9 grids and find the ones that satisfy the rules AND are consistent with the "known" numbers. That would make it O(1), not NP-hard.
> For (1) and (2), the worst-case just doesn't occur.
I don't think 2. is a good example to be honest, It happens quite a lot. At least it's definitely not in the same category as dependency resolution, where people often don't even know that it's NP-hard.
Typescript, Rust or C++ type system complexity is routinely a compile time problem that people have to work around or tackle from both sides (i.e. either changing the compiler or changing the program).
True, but this has very little to do with these being NP-hard.
As an example I know well: In Rust, exhaustiveness checking is NP-complete, and trait solving is undecidable. Exhaustiveness checking contributes basically nothing to compile times, and trait solving is significant but that's only because we do it many many times, each particular instance is solved very quickly (and we have limits for how long it can go). Optimizations of both are done using programming tricks and not via algorithmic improvements, almost always.
Various crates have explicit workarounds for these issues as well, typically using Box to avoid deep types, e.g. axum's `.route()` added it explicitly to avoid this, I believe.
For match exhaustivness, there's currently an active discussion on it again, because it comes up in derives for big enums, and we just landed an optimization that avoids it for some derive macros.
In other ecosystems, I remember a talk about avoiding exponential blowup for various constructs in C++ templates. Typescript even has a guide for how to write types to avoid complexity problems. With libriaries like `ArkType`, people hit these issues a quite a bit.
I won't claim that this is the majority of the compile time work, but it's something that comes up often enough that I think it's pretty ridiculous to say "the worst-case just doesn't occur."
I had some tedious debate on HN once where I asked if anyone had any pointers to good parallel SMT solvers, only to fall victim to someone dedicated to dying on the hill of "parallelization can never make this kind of search faster" due to (often inapplicable) complexity theory fixation.
I have, it's called conda.
One interesting example is metric TSP versus general TSP. We are used to traveling salesman problem on a map with distances that obey the triangle inequality. This admits an easy heuristic solution to an approximation factor of 2 (just do minimum spanning tree twice). However, nonmetric TSP is not approximable (to a constant factor of the optimal value in polynomial time (unless P=NP)).
Have you ever tried building an iOS app? The compiler gives up after a sufficient time because typechecking can be so slow
I feel that is similar to how adding randomness to cryptography [1] opened a bunch of new systems like zero knowledge proofs[2]. By allowing us to be wrong in a very small number of instances (arbitrarily small by adjusting things like key size), we can build practical systems with really impressive properties.
[1]: Goldwasser and Micali - Probabilistic Encryption, 1983 https://web.archive.org/web/20090319000035/http://groups.csa... [2]: Goldwasser, Micali and Rackoff - The knowledge complexity of interactive proof-systems, 1985 https://courses.csail.mit.edu/6.857/2008/handouts/1989-siamj...
Consider the vertex cover problem where you want to cover all edges of a graph by at most k vertices (that are incident to all edges). It is a classical NP-complete problem and the naive bruteforce solver needs something like n^k time. Which is already huge for small k, say, 10.
A very simple fixed-parameter tractable (fpt) algorithm for this problem achieves a worst case time of 2^k * n. For huge graphs and small k (again, let’s say 10) this is a massive improvement.
This is a very active field, where we have a good understanding which problems allow have such a worst case time and which not (under some complexity theoretic assumptions of course). It incorporates also the idea of restricting the input to only specific „simple“ instances gradually. This happens if you add graph measures as a parameter.
Many NP-hard graph problems are in P if restricted to planar graphs. But what if the instances are „almost“ planar? If you choose a parameter that measures the structure of a graph such that the measure is low if the graph is planar and high if it isn’t, any fpt algorithm for this parameterization works on any graph; fast if it is planar, and fast-ish if it is close to being planar.
Of course, this is theory with the similar metaphysical caveats classical complexity theorem has. However, it results in interesting algorithmcsl tools and interacts nicely with specific fields of structural graph theory.
(not necessarily an LLM, AI is a huge field)
I don't think their aim is to dissuade people from running approximate optimization against np. At least that was certainly never my takeaway, but maybe some courses/lecturers don't make that clear enough.
If your larger point is that comp sci cares too much about theory for the average programmer, sure. Maybe there should be a different degree program for software "engineering". But I think that's true of most degrees. Maybe comp sci is special because it's treated as a science whereas most people take it to be engineers. But coming from physics as just an example, the majority of people become engineers or something else not-professional-physics. But I sure as hell hope they don't go less proof-heavy in physics courses because many people will never never be able to prove something again in their lives.
A lot of professors don't teach this, and it's recklessly ignorant if not worse.
Both of these problems have been hand crafted and sanded down so as not to get into situations where there's exponential blow up.
> [Scheduling] and [Traveling Salesman] are technically optimization problems. Everyone knows you can tackle those with heuristics, ... We absolutely have tools that can find provably optimal solutions in reasonable time. There's no magic. No quantum computers. Just thinking harder and coming up with better algorithms. ... algorithmic speedup has outpaced hardware gains in the last decades. ...
The tools that can "absolutely find optimal solutions" don't, for even toy problems. Thinking harder helps, sometimes, but barely scratches the surface of most of these problems. Most of the time, thinking harder doesn't magically solve these problems.
> Last but not least: even (5), the archetype of NP-hard problems, is routinely solved at scale.
If this were even remotely true we'd have seen substantial progress in automated theorem proving well before the last couple of years. Notice how there are many math problems succumbing to automated techniques? This isn't because SAT solvers "routinely solve this at scale", it's because LLMs are getting better.
Why do we need type checking in the first place? One reason is to help find bugs. We need to enforce type checking to reduce bugs because reducing programs to SAT to ensure they're bug free is intractable. SAT is solved at scale? Why haven't they made solvers to prove your code is bug free so you don't need type checking in the first place?
I'm not up on scheduling software or research but my bet is that people who actually write schedulers would say that those tools that "absolutely" solve the problem absolutely don't.
The post almost gets it but never quite makes the leap. Taking Turing machines, for example. It's pretty easy to show that the Halting problem is undecidable. It doesn't mean all programs can't be analyzed, it means that there's no general method that will work for all programs. We don't give up on writing programs, we restrict ourselves to programs that we can reason about.
The ensemble, the space of problems we draw from, is specifically chosen so that we can do interesting work. But even that's restrictive and we're trying to constantly push to see what other programs we can analyze that are past our current front of knowledge.
This reads like child going into a supermarket and declaring farming, logistics and food scarcity to be solved because of the abundant availability of goods on the shelf. The world we've made is specifically crafted so that normal use is smooth. The fact you can't see it means you're living in a coddled domain and haven't pushed past it.
Chapter one starts with a fictional example. Say you have been trying to develop an algorithm at work that validates designs for new products. After much work you haven't found anything better than exhaustive search, which is too slow.
You don't want to tell your boss "I can't find an efficient algorithm. I guess I'm just too dumb".
What you'd like to do is prove that the problem is inherently intractable, so you could confidently tell your boss "I can't find an efficient algorithm, because no such algorithm is possible!".
Unfortunately, the authors note, proving intractability is also often very hard. Even the best theoreticians have been stymied trying to prove commonly encountered hard problems are intractable. That's where the theory of NP-completeness comes in:
> However, having read this book, you have discovered something almost as good. The theory of NP-completeness provides many straightforward techniques for proving that a given problem is “just as hard” as a large number of other problems that are widely recognized as being difficult and that have been confounding the experts for years.
Using the techniques from the book you prove the problem is NP-complete. Then you can go to your boss and announce "I can't find an efficient algorithm, but neither can all these famous people". The authors note that at the very least this informs your boss that it won't do any good to fire you and hire another algorithms expert. They go on:
> Of course, our own bosses would frown upon our writing this book if its sole purpose was to protect the jobs of algorithm designers. Indeed, discovering that a problem is NP-complete is usually just the beginning of work on that problem.
...
> However, the knowledge that it is NP-complete does provide valuable information about what lines of approach have the potential of being most productive. Certainly the search for an efficient, exact algorithm should be accorded low priority. It is now more appropriate to concentrate on other, less ambitious, approaches. For example, you might look for efficient algorithms that solve various special cases of the general problem. You might look for algorithms that, though not guaranteed to run quickly, seem likely to do so most of the time. Or you might even relax the problem somewhat, looking for a fast algorithm that merely finds designs that meet most of the component specifications. In short, the primary application of the theory of NP-completeness is to assist algorithm designers in directing their problem-solving efforts toward those approaches that have the greatest likelihood of leading to useful algorithms.
While not novel its a pity warrants a legitimate HN front page.