1. The study of complexity classes isn't intended to dissuade people from writing certain programs. It's intended to understand the nature and theoretical limits of computation. As far as practice goes, it can be used to show where heuristics are needed. Saying it's overrated is like saying calculus is overrated because most people don't need to use it every day. And BTW, many important problems are in classes believed to be way harder than NP (i.e. NP-complete is the easiest of the hard famous complexity classes). E.g., I've seen some people brag about some configuration language being easy to mechanically analyse because it's not Turing-complete, while in fact it's at least PSPACE-hard to analyse.
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.
> E.g., I've seen some people brag about some configuration language being easy to mechanically analyse because it's not Turing-complete, while in fact it's at least PSPACE-hard to analyse.
Isn't even just the question of minimising the length of a regular expression PSPACE-hard or so?
> Saying it's overrated is like saying calculus is overrated because most people don't need to use it every day.
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.
> For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions
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.
> The article was showing the difference between mathematicians and engineers.
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.
Some mathematicians certainly did, but there's a very large undercurrent in CS, as well as Mathematics more in general, of utter disinterest for applications as well as the idea that the more general a solution, the more "worthy" it is. That was really obvious from the words of the professor cited in the article.
You have clearly not encountered theoretical computer scientists. They love to create all kinds of complexity classes and theorems to capture things like heuristics and approximation algorithms and other things which work in practice but not theory.
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
I studied mathematics, and can attest that the attitude of the professor mentioned in the article is very representative of an older generation of mathematicians. Maybe the younger ones are different.
> It's intended to understand the nature and theoretical limits of computation.
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.
Standard complexity theory focuses on answering questions when our substrate behaves like a Turing machine with multiple tapes.
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.
We actually understand quite a bit about the universe and the kinds of computers we can build. People also think about computers in speculative physics scenarios, eg closed timelike curves can be used to solve pspace complete problems.
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.
> Standard complexity theory focuses on answering questions when our substrate behaves like a Turing machine with multiple tapes.
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.
> there is a reduction of known complexity between two models.
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.
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.
I feel like the write up doesn't really engage with the number one solution used
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
Another way to look at it is that in practice N is typically bounded by a large constant, making the time complexity effectively O(1).
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.
And then you encounter packages with `setup.py` that generates a random list of dependencies on each run. You can't know the dependencies without running code.
> Dependency managers tend to just block a huge category of situations that effectively eliminate the entire NP hard space
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.
Presumably the ones where you are expected to have the latest version of everything and make a new package if you break that (python2 → python3)
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.
> Building a SAT solver into the package manager seems to be a solution in search of a problem.
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.
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.)
Very true! What makes NP-hard problems difficult is almost always the combinatorial explosion related to specific problem configurations -- you can construct instances given an approximate heuristic or branch-and-bound solver that will cause it to have an exponential blow up. But for most practical problems you don't reach those explosive configurations.
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.
>For (1) and (2), the worst-case just doesn't occur. 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.
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.
The description you've given for apt just sounds almost exactly like SAT, a problem that's very efficiently approximated. That's exactly how the --solver 3.0 flag on recent apt versions works [0].
I'm fond of this brain-expander, in spirit of TFA: "Did you know travelling salesperson is O(N) on a large class of graphs?"
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.
At risk of disclosing certain personal details about myself on the internet, I pinky-promise that the two aren't as different as folks without certain cognitive limitations might think.
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 one that comes to mind is how big your hash maps have to get before all the clever algorithms beat linear scan, and it's surprisingly large on modern computers: linear memory access is _very_ predictable.
The Roc and Zig folks probably have actual numbers.
What are these surprisingly large numbers you've seen? I thought that linear scan optimizations are typically reserved for pretty small maps, like dozens or maybe hundreds of elements.
Not sure if this counts, but I learned Huffman coding the intuitive tree-based way. From memory it was O(nlogn), but you can just O(n) it in-place in an array.
Huffman decoding you mean. All the fast decoders build tables processing N (8, 16, ...) bits at a time. If the next byte is 253 in state 6 that means output 15,28,28 and go to state 42...
There are probably even faster ways I don't know of.
I spent my career in electronic design automation, where practically every interesting problem is NP-hard, but we have to solve them, or approximately solve them at least, and because real-life problems often have structure, with the right approach very large problems can be solved exactly despite the theoretical complexity, and when exact solutions can't be found a decent bound can often be found that is an acceptable solution.
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.
Sometimes you don't need an _exact_ solution. approximation of the traveling salesman problem exists for the metric version, it's O(n^3), and produces a result that's not worse than 50% of the optimal result, and for the general case O(n^2) algorithm exists that produces a result that costs at most twice the optimal result.
For traveling salesman that's more than good enough. But in many cases an O(n^3) algorithm can't be used because n is in the billions. I remember interviewing a candidate who asserted that register retiming in digital circuits was a non-problem, so they were surprised that we were still working on improvements, because they had learned that the Leiserson-Saxe algorithm gives an optimal solution in O(n^3) time. But because real circuits are so large that that approach can't be used. Polynomial time often isn't good enough; even quadratic time often isn't tolerable.
> 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.
> The theory is not wrong, but in practice it's often irrelevant. Sure, any algorithm you can come up with will blow up on some inputs. But you might get a fast solution on 99.9% of inputs.
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.
The neural network approach should be able to crush any NP-hard problem into an easy problem for the subset of real world examples, although not for all possible examples.
A well known NP-hard problem is matching some flavors of regex (ex: PCRE). You can turn a 3-SAT problem into such a regex.
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.
Actually, regices with really bad running times are a known vulnerability class. For example (a) is exponential (factorial maybe?) and if you try to match user input against (a) someone who enters a long string of a followed by a single b will bring down your server.
Good point. The number of times is zero. Probably something that should be implemented defensively at the library level. I guess most developers don't realise this can happen (I did not).
I actually did add a timer as a final "if all else fails" for my regex implementation rather recently, maybe 6 months ago. I don't even know of any scenario that could reach the timer because I have a robust allowlist/denylist and a ton of unit tests. But I would rather just be certain and it wasn't hard.
No you don't actually want a regex library that randomly fails when someone runs one of Chris Domas's pathological stall instructions on a different core.
The author justifiably attacks the notion that "NP-hard" == "too hard to solve in practice", but then makes the opposite error:
> 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?
Reminds me of Rich Hickey's clojure data structures. Yes, they're technically log_32(n) complexity, but it turns out log 32 is basically flat on any normal machine, thus "practically constant".
This dovetails into one of my favorite CS sub-fields: approximation algorithms. In many cases NP-Hard problems may be approximated with a guaranteed lower bound of accuracy. For example, solving the euclidean version of the travelling salesman problem using a minimum spanning tree finds solutions that are no worse than 1.5 times the true minimum length, and there are heuristics with weaker guarantees that consistently perform better in practice.
That is proximal to one of my peeves in this space: People who misunderstand approximation results to be meaningful when often they're not.
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.
NP-hard just speaks about the algorithm complexity. The input size of a typical sudoku puzzles so small that even the most naive algorithm can do it quickly.
Incorrect. I tried the most naive algorithm when I was about 9. It generated every 9x9 grid of digits, checked if it was a Sudoku solution, and then it it matched the puzzle. I gave up while every row but the first was still full of 0s.
The general version of a problem being NP-complete doesn't mean that cases of practical interest are all necessarily intractable. In the case of SAT, for instance, there are also ways for the humans to give the solver an easier problem to solve in many cases, like adding extra clauses to guide the solver away from useless parts of the search space.
Just an example: Klondike (the solitaire game) is NP-hard (and, if I remember correctly, NP-complete) and it never stopped players from playing it, or developers from implementing it, even though it's sometimes impossible to know if the given setup has a solution at all, or not.
> For (1) and (2), the worst-case just doesn't occur. 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.
Hehe, clearly the author hasn't written any SwiftUI.
I think that Swift is the exception that proves the rule. The fact that it is notorious for giving up on certain type checks indicates that it isn't a problem for most languages.
It's the other way around, I think: it's not a problem for most languages because bidirectional type inference with overloading is NP-hard. It'd be nice to have, but it's impossible to implement in a way that's reliably fast, so it's not even considered as an option.
Ever since I first saw a binary integer program with millions of variables solved in less time than it took me to hit enter I realized that the fact that I had made it through graduate school for computer science, and never encountered the sorts of optimization algorithms happening in the field of operation operations research is a sad one.
Don't feel bad, after an undergrad degree and over 30 years in the field I still have to look up exactly what NP, NP hard, and NP complete means every time I see them.
OR has some very interesting algorithms for very interesting problems. I don't do research on it anymore, but going to OR conferences was always interesting. Good mix of practitioners, researchers and end users. I'm way behind SOTA now, but I have a soft spot for evolutionary algorithms.
> NP-hard problems are solvable in theory but it's hopelessly expensive in practice. It's basically proven that no good algorithms exist. At least that's what I took away.
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.
In Python there are definitely times with large environments where you get combinatorial corners where things go exponential -- at scale processing user workloads and environments we've definitely hit sharp corners here. Switching to better and faster resolution systems have improved things significantly (because even the exponential case reduces to wall-clock times that aren't terrible) but you definitely hit those corners because Python is very architecturally bad for how it specified package dependencies.
If you're going to wrote a blog post on the topic, probably worth spending a few minutes double checking your understanding of the "thing". I don't doubt that the author may have been taught the wrong thing, but to write an entire post starting from and remaining in a state of misunderstanding is not particularly useful.
The entire point of the article is that his original understanding of the “thing” was a misunderstanding, with a heavy emphasis on how his teachers led him to that misunderstanding.
Author used a rhetorical device that you seem to have missed.
The article brings with an incorrect premise, and then argues a different point.
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.
> At the time, my professor closed the final lecture with dramatic words (I'm paraphrasing slightly):
>>> 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.
This is kind of why P vs NP is such an interesting problem. It seems that a big family of NP-hard problems in fact _can_ be solved efficiently if we allow relaxing some constraints, like optimality (eg TSP), or generality of our algorithm (eg type checking).
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.
This is still a theoretical problem. Whether or not a particular problem class admits and approximation or an arbitrarily good approximation is often of theoretical interest.
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)).
In the classic 1979 book "Computers and Intractability: A Guide to the Theory of NP-Completeness" by Garey & Johnson, here's how they explain what it means for the practicing programmer.
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.
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.
It's worth noting this cuts both ways. An NP-complete problem may wind-up having only a few instances that are exponential in the inputs but a problem that is "only" O(input-size^3) is going to be difficult to deal for input of significant size.
1. The study of complexity classes isn't intended to dissuade people from writing certain programs. It's intended to understand the nature and theoretical limits of computation. As far as practice goes, it can be used to show where heuristics are needed. Saying it's overrated is like saying calculus is overrated because most people don't need to use it every day. And BTW, many important problems are in classes believed to be way harder than NP (i.e. NP-complete is the easiest of the hard famous complexity classes). E.g., I've seen some people brag about some configuration language being easy to mechanically analyse because it's not Turing-complete, while in fact it's at least PSPACE-hard to analyse.
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.
[1]: https://en.wikipedia.org/wiki/Parameterized_complexity
> E.g., I've seen some people brag about some configuration language being easy to mechanically analyse because it's not Turing-complete, while in fact it's at least PSPACE-hard to analyse.
Isn't even just the question of minimising the length of a regular expression PSPACE-hard or so?
> Saying it's overrated is like saying calculus is overrated because most people don't need to use it every day.
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.
> For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions
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.
> For the mathematicians that created Computation Science, the only interesting solutions are complete solutions to general questions
There is a bunch of research devoted to Polynomial Time Approximation Schemes (PTAS). Mathematicians also take part in it.
> The article was showing the difference between mathematicians and engineers.
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.
Some mathematicians certainly did, but there's a very large undercurrent in CS, as well as Mathematics more in general, of utter disinterest for applications as well as the idea that the more general a solution, the more "worthy" it is. That was really obvious from the words of the professor cited in the article.
Would you disagree that, given the choice, a solution to every problem is strictly better than a solution so only some problems?
No. Because for let’s say the halting problem the general case says it’s unsolvable, but each specific case is solvable.
You have clearly not encountered theoretical computer scientists. They love to create all kinds of complexity classes and theorems to capture things like heuristics and approximation algorithms and other things which work in practice but not theory.
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
I studied mathematics, and can attest that the attitude of the professor mentioned in the article is very representative of an older generation of mathematicians. Maybe the younger ones are different.
> It's intended to understand the nature and theoretical limits of computation.
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.
>Not in a general sense, at least for standard complexity theory. It only deals with a very specific model of computation.
What is an example of a model of computation where complexity theory doesn't apply?
Standard complexity theory focuses on answering questions when our substrate behaves like a Turing machine with multiple tapes.
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.
We actually understand quite a bit about the universe and the kinds of computers we can build. People also think about computers in speculative physics scenarios, eg closed timelike curves can be used to solve pspace complete problems.
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.
> Standard complexity theory focuses on answering questions when our substrate behaves like a Turing machine with multiple tapes.
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).
> there is a reduction of known complexity between two models.
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.
Isn't complexity theory usual based on a random-access model, not any kind of Turing machine?
MT Turing machines aren't really all that different. Or from pointer machines for that matter. They map nicely together.
I feel like the write up doesn't really engage with the number one solution used
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
Another way to look at it is that in practice N is typically bounded by a large constant, making the time complexity effectively O(1).
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.
10000?
Wait until you meet pip and liberal requirements.txt
And then you encounter packages with `setup.py` that generates a random list of dependencies on each run. You can't know the dependencies without running code.
> Dependency managers tend to just block a huge category of situations that effectively eliminate the entire NP hard space
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.
Presumably the ones where you are expected to have the latest version of everything and make a new package if you break that (python2 → python3)
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.
> Building a SAT solver into the package manager seems to be a solution in search of a problem.
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.
A variant:
> 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.)
Don't allow the hard ones makes the problems P doesn't it?
Kind of the point yes
Exactly!
Very true! What makes NP-hard problems difficult is almost always the combinatorial explosion related to specific problem configurations -- you can construct instances given an approximate heuristic or branch-and-bound solver that will cause it to have an exponential blow up. But for most practical problems you don't reach those explosive configurations.
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.
>For (1) and (2), the worst-case just doesn't occur. 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.
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.
The description you've given for apt just sounds almost exactly like SAT, a problem that's very efficiently approximated. That's exactly how the --solver 3.0 flag on recent apt versions works [0].
[0] https://blog.jak-linux.org/2024/05/14/solver3/
I'm fond of this brain-expander, in spirit of TFA: "Did you know travelling salesperson is O(N) on a large class of graphs?"
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.
Yeah why is "the algorithm" the thing we do in our head to mimick a 1970s computer and not what really happens on hardware.
At risk of disclosing certain personal details about myself on the internet, I pinky-promise that the two aren't as different as folks without certain cognitive limitations might think.
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 ".
Why is it a limitation to know about SIMD, AVX, L1 cache etc.? Or am I missing your point?
Do you have any examples of the second class?
The one that comes to mind is how big your hash maps have to get before all the clever algorithms beat linear scan, and it's surprisingly large on modern computers: linear memory access is _very_ predictable.
The Roc and Zig folks probably have actual numbers.
What are these surprisingly large numbers you've seen? I thought that linear scan optimizations are typically reserved for pretty small maps, like dozens or maybe hundreds of elements.
Hundreds sounds about right, maybe up to a thousand.
But nobody expects that. Hashmap is supposed to be faster once you have, like, ten elements. That's what was promised to us.
Yeah, I found hundreds surprising (although not on reflection).
Depends on comparison function. In clickhouse-c for type name lookup it's strcmp so I use generated hash table with no collisions & reusing cityhash function since we have it handy: https://github.com/ClickHouse/clickhouse-c/blob/4bdd89a02438...
Benchmarked an order of magnitude faster than linear scan or binary search. I agree with your general sentiment tho, which is why I measured
Not sure if this counts, but I learned Huffman coding the intuitive tree-based way. From memory it was O(nlogn), but you can just O(n) it in-place in an array.
Huffman decoding you mean. All the fast decoders build tables processing N (8, 16, ...) bits at a time. If the next byte is 253 in state 6 that means output 15,28,28 and go to state 42...
There are probably even faster ways I don't know of.
> 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.
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.
Exactly.
Debian allow you to choose different solver (typical Debian). It is easy to get galactic blow up if you insist.
I spent my career in electronic design automation, where practically every interesting problem is NP-hard, but we have to solve them, or approximately solve them at least, and because real-life problems often have structure, with the right approach very large problems can be solved exactly despite the theoretical complexity, and when exact solutions can't be found a decent bound can often be found that is an acceptable solution.
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.
Sometimes you don't need an _exact_ solution. approximation of the traveling salesman problem exists for the metric version, it's O(n^3), and produces a result that's not worse than 50% of the optimal result, and for the general case O(n^2) algorithm exists that produces a result that costs at most twice the optimal result.
For traveling salesman that's more than good enough. But in many cases an O(n^3) algorithm can't be used because n is in the billions. I remember interviewing a candidate who asserted that register retiming in digital circuits was a non-problem, so they were surprised that we were still working on improvements, because they had learned that the Leiserson-Saxe algorithm gives an optimal solution in O(n^3) time. But because real circuits are so large that that approach can't be used. Polynomial time often isn't good enough; even quadratic time often isn't tolerable.
Twice the optimal result is terrible, though.
Luckily, there are pretty good heuristic solutions that work well in practice.
That's worst case. It means the most adversarial graph imaginable gets a time twice as long as the shortest possible.
> A few prominent NP-hard problems:
> 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.
> The theory is not wrong, but in practice it's often irrelevant. Sure, any algorithm you can come up with will blow up on some inputs. But you might get a fast solution on 99.9% of inputs.
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.
The neural network approach should be able to crush any NP-hard problem into an easy problem for the subset of real world examples, although not for all possible examples.
Perfect example is the simplex algorithm.
We do have a polynomial algorithm for linear programming yet simplex (with exponential worst case performance) is our tool of choice.
Mostly as a subproblem solver for mixed-integer programs, due to ease of warm-start. MIP itself is NP (B&B), so NP*NP=NP
A well known NP-hard problem is matching some flavors of regex (ex: PCRE). You can turn a 3-SAT problem into such a regex.
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.
Actually, regices with really bad running times are a known vulnerability class. For example (a) is exponential (factorial maybe?) and if you try to match user input against (a) someone who enters a long string of a followed by a single b will bring down your server.
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...
If a regex runs too long just kill it and show the user an error.
How often have you encountered code that adds a timeout to regex matching?
Good point. The number of times is zero. Probably something that should be implemented defensively at the library level. I guess most developers don't realise this can happen (I did not).
I actually did add a timer as a final "if all else fails" for my regex implementation rather recently, maybe 6 months ago. I don't even know of any scenario that could reach the timer because I have a robust allowlist/denylist and a ton of unit tests. But I would rather just be certain and it wasn't hard.
No you don't actually want a regex library that randomly fails when someone runs one of Chris Domas's pathological stall instructions on a different core.
Why do you say "randomly fails"? Do you consider a configurable timeout with an exception to be a random failure?
What do you want it to do under those conditions then? Stall pathologically?
The author justifiably attacks the notion that "NP-hard" == "too hard to solve in practice", but then makes the opposite error:
> 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?
Author here. I agree, I should add more hedging:
> 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
Reminds me of Rich Hickey's clojure data structures. Yes, they're technically log_32(n) complexity, but it turns out log 32 is basically flat on any normal machine, thus "practically constant".
This dovetails into one of my favorite CS sub-fields: approximation algorithms. In many cases NP-Hard problems may be approximated with a guaranteed lower bound of accuracy. For example, solving the euclidean version of the travelling salesman problem using a minimum spanning tree finds solutions that are no worse than 1.5 times the true minimum length, and there are heuristics with weaker guarantees that consistently perform better in practice.
That is proximal to one of my peeves in this space: People who misunderstand approximation results to be meaningful when often they're not.
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.
One example is Sudoku. It's NP-hard, but in practice, it takes no time at all to solve your newspaper puzzle.
NP-hard just speaks about the algorithm complexity. The input size of a typical sudoku puzzles so small that even the most naive algorithm can do it quickly.
Incorrect. I tried the most naive algorithm when I was about 9. It generated every 9x9 grid of digits, checked if it was a Sudoku solution, and then it it matched the puzzle. I gave up while every row but the first was still full of 0s.
Ok yes. I suppose it is possible to do worse than brute force, haha
The general version of a problem being NP-complete doesn't mean that cases of practical interest are all necessarily intractable. In the case of SAT, for instance, there are also ways for the humans to give the solver an easier problem to solve in many cases, like adding extra clauses to guide the solver away from useless parts of the search space.
Just an example: Klondike (the solitaire game) is NP-hard (and, if I remember correctly, NP-complete) and it never stopped players from playing it, or developers from implementing it, even though it's sometimes impossible to know if the given setup has a solution at all, or not.
> For (1) and (2), the worst-case just doesn't occur. 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.
Hehe, clearly the author hasn't written any SwiftUI.
I think that Swift is the exception that proves the rule. The fact that it is notorious for giving up on certain type checks indicates that it isn't a problem for most languages.
It's the other way around, I think: it's not a problem for most languages because bidirectional type inference with overloading is NP-hard. It'd be nice to have, but it's impossible to implement in a way that's reliably fast, so it's not even considered as an option.
Got examples for non-Swift programmers?
Most expressions with overloads are a disaster in swift: https://www.cocoawithlove.com/blog/2016/07/12/type-checker-i...
https://archive.ph/C0jGr
Author here. I have indeed not.
> 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.
I have, it's called conda.
Ever since I first saw a binary integer program with millions of variables solved in less time than it took me to hit enter I realized that the fact that I had made it through graduate school for computer science, and never encountered the sorts of optimization algorithms happening in the field of operation operations research is a sad one.
Don't feel bad, after an undergrad degree and over 30 years in the field I still have to look up exactly what NP, NP hard, and NP complete means every time I see them.
A good deal of the field of Operations Research (OR) is about getting a good solution to NP-hard problems anyway. It is fun!
OR has some very interesting algorithms for very interesting problems. I don't do research on it anymore, but going to OR conferences was always interesting. Good mix of practitioners, researchers and end users. I'm way behind SOTA now, but I have a soft spot for evolutionary algorithms.
My 5 years in school timetabling say: 100% agree!
> 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.
Have you ever tried building an iOS app? The compiler gives up after a sufficient time because typechecking can be so slow
That only happens with swift, which is dogshit. They allegedly fixed it but anyone worth a damn left long before that
> NP-hard problems are solvable in theory but it's hopelessly expensive in practice. It's basically proven that no good algorithms exist. At least that's what I took away.
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.
In Python there are definitely times with large environments where you get combinatorial corners where things go exponential -- at scale processing user workloads and environments we've definitely hit sharp corners here. Switching to better and faster resolution systems have improved things significantly (because even the exponential case reduces to wall-clock times that aren't terrible) but you definitely hit those corners because Python is very architecturally bad for how it specified package dependencies.
Package managers could stop being NP hard by taking away negative dependencies, including maximum version limits
> You took away the wrong thing
I'm more willing to believe they were taught the wrong thing.
If you're going to wrote a blog post on the topic, probably worth spending a few minutes double checking your understanding of the "thing". I don't doubt that the author may have been taught the wrong thing, but to write an entire post starting from and remaining in a state of misunderstanding is not particularly useful.
The entire point of the article is that his original understanding of the “thing” was a misunderstanding, with a heavy emphasis on how his teachers led him to that misunderstanding.
Author used a rhetorical device that you seem to have missed.
The article brings with an incorrect premise, and then argues a different point.
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.
No doubt.
And if the problem is really really hard, you can throw an AI at it and hopefully get a probabilistic solution.
(not necessarily an LLM, AI is a huge field)
Basically every optimization heuristic one might use is technically AI, so yes
> At the time, my professor closed the final lecture with dramatic words (I'm paraphrasing slightly):
>>> 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.
This is kind of why P vs NP is such an interesting problem. It seems that a big family of NP-hard problems in fact _can_ be solved efficiently if we allow relaxing some constraints, like optimality (eg TSP), or generality of our algorithm (eg type checking).
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...
How come most package managers suck then? Why did I waste hours of my life debugging portage and yum?
Once you admit approximations the theoretical problem trades places with a more interesting one: what is the Pareto frontier of loss vs complexity?
This is still a theoretical problem. Whether or not a particular problem class admits and approximation or an arbitrarily good approximation is often of theoretical interest.
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)).
Does minimum spanning tree rely on the triangle inequality? I thought it worked on arbitrary graphs
In the classic 1979 book "Computers and Intractability: A Guide to the Theory of NP-Completeness" by Garey & Johnson, here's how they explain what it means for the practicing programmer.
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.
Did you know: general purpose computers are completely pointless, because programs can run forever without producing a result.
I've made comments on HN on this point a number of times e.g. https://news.ycombinator.com/item?id=44284083
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.
It's worth noting this cuts both ways. An NP-complete problem may wind-up having only a few instances that are exponential in the inputs but a problem that is "only" O(input-size^3) is going to be difficult to deal for input of significant size.
Like matrix multiplication! That's N^3 naively. If you take N to be the size of each dimension.
tl;dr NP-hard isn't that hard if you relax constraints.
While not novel its a pity warrants a legitimate HN front page.