Funnily enough this very morning I asked an LLM to implement an algorithm for an NP-hard problem (a variation of the knapsack problem). I gave it 2 directives:
* 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.
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.
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.
> 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).
> 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.
I did study a bit of complexity theory back in the day, and it does seem a bit theoretical, but not so long ago, I ran into an very prominent manifestation. To help someone, I had created a simple web page which also had an input field for the css that was applied directly to the page. To avoid flickering and weird effects because of malformed css, I wrote a regexp to check the CSS code. It's a very simple language, after all, and it didn't have to be perfect. It worked well, until at one point, a simple typo locked up Chrome for 1 minute 10 seconds. Parse time just jumped from less than 100ms to 70000ms by adding a single character. That's when you feel what exponential means.
> 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.
I would to say I support that view. What is the purpose of modern science if not to discover truths you can apply universally? If you state: ‘this particular apple falls to the ground’ thats not a scientific discovery, there must be some general applicability.
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.
I also studied mathematics, and I can tell you that this was not my experience.
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.
> 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].
Yes, apt's solver has always been very fast. I still use aptitude only because it is interactive, and when apt just gives up with 0 to upgrade, 283 not upgraded the interactive exploration helps a lot.
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.
Maybe more than that if you have a sub-optimal hash map implementations. There are a bunch of those floating around - for example, Java's build-in HashMap has traditionally been kneecapped by lack of value types, and if you are not careful you can incur 2x cache misses per lookup...
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.
You can't do it faster than O(n log n) for the simple reason that you need to sort the frequencies. If the symbols come sorted, then you can do it in O(n) time, yes, using two queues.
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'm sort of in this boat right now. I wrote an algorithm to solve a problem, and it turns out to be roughly O(n!), which is really terrible, but it works fine in all my test cases because n never gets bigger than 20. Even in real life cases, I doubt n will ever be larger than 40 (which is where it starts to break down).
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.
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.
> 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.
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.
> 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).
> Typescript, Rust or C++ type system complexity is routinely a compile time problem that people have to work around or tackle from both sides
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.
> 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.
Why are they writing their own constraint solver? There are so many great off-the-shelf constraint solvers that are probably going to be way faster than whatever Swift engineers can cook up.
> 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.
When you say "The neural network approach"... you are effectively refining the problem space into something smaller based on the data that you are training the NN on.
(Note: I'm speaking vaguley, on the same vague level as your comment. I can be more precise as to what my indications indicate)
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?
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.
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.
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.
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.
Technically, Sudoku as normally defined can't be in any complexity class because there are only a finite number of 3x3 Sudoku. People say "Sudoku is NP-hard" to mean a generalized NxN Sudoku would be NP-hard. But no one would expect that to be easy.
Another interesting NP-complete problem is minesweeper and closer to true since minesweeper problems can have variable size by their definition.
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.
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".
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.
> For [Dependency resolution] and [Type checking], the worst-case just doesn't occur. ... at least in my career, I've never seen a galactic blow-up.
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.
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.
A personal favorite of mine is fixed-parameter tractability. Instead of analysing the worst case running time solely on the input length we introduce a *parameter* and study the time complexity in both. Intuitively, the parameter „should“ be small and is often chosen to be the solution size or some specific measure of the input.
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.
> 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.
The algorithms listed were intentionally chosen to be easy to solve.
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".
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.
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)).
You’re right, it doesn’t. However, in TSP you are allowed to visit each vertex *exactly* once. So traversing the minimum spanning tree naively is not a valid solution. What you the approximation does is to „shortcut“ the paths if you would revisit an already seen vertex again. That’s where you need the triangle inequality to guarantee that the shortcut isn’t longer than the path through the minimum spanning tree. Otherwise you cannot guarantee an approximation ratio of at most 2.
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.
It is indeed very interesting. For the latter the concepts from fine-grained complexity and average time are interesting. For specific problems, there are theoretical fine grained lower bounds for time complexity (i.e. cannot be solved in (truly) subcubic time). However, these rely on assumptions that are even stronger than P != NP.
* 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.
reply