NP-complete isn't always hard

Great essay. Maybe another thing to note is that in industry we often don't need the singular best answer, but one that is "close" or "good". In fact, sometimes this is a requirement - like a sudoku solver that can handle impossible boards by generating a solution with a small number of collisions.

As evidenced by the fact that traveling salespeople exist (and are not, in general modeling experts or big AWS users), approximate solutions are often significantly easier to find - both practically and in theory.

I bring this up because it's interesting... and because my professors really didn't emphasize it until deep into my undergraduate career. So someone today might be one of today's lucky 10,000.

Modeling of problems is something that feels like a lost art. And completely a subtext in so much of what programmers discuss.

What I mean by subtext is that OO is a way to model a problem as much as it is a way to organize code. Same for what we often call functional. Yet we spend far more time and effort talking only about what it means to organize the code, with kind of a byline on how it helps to model the solution.

I do think it is there, but by the time you show someone how a SAT solver is just working on the true/false of various variables, and that it often can be seen as "learning" combinations of those variables that are known true/false, that is so far away from the typical understanding of the problem that it looks alien.

Two years ago I had to create a quarterly schedule for a team of four, and about 20 tasks with dependencies.

I had just read a piece about using SAT solvers for designing keys and locks that was on HN, and decided to model my problem as a SAT problem.

An hour later (about 59:30 coding, 00:30 minicrypto3 running), I had the perfect schedule! It was optimal since it was also proven to be the shortest time to do all tasks.

No one caring about this schedule and it didn't matter - one hours work. The joy I got from the exercise - priceless.

Probably would have been better to use the word 'difficult' because NP-complete does in fact automatically imply NP-hard. I was expecting a very different article based on the title.

Haskell type inference is EXPTIME, O(2^p(n)), yet it works fine in practice. This reminds me of the quote by Rob Pike on algorithms completely:

>>Rule 3. Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don’t get fancy.

https://en.m.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_...

The article explains the P vs NP issue [1] very well. If there is one thing to nitpick, then

> in fact “convert NP-complete problem to SAT” is in P.

is not the most precise, since P is a class of decision problems, while said conversion [2] is not a decision problem, but something that runs in polynomial time.

[1] https://en.wikipedia.org/wiki/P_versus_NP_problem

[2] https://en.wikipedia.org/wiki/Polynomial-time_reduction

> This is true in principle, but the reality is more complicated. When we say “NP-complete is hard” we’re talking about worst-case complexity, and the average-case complexity is often much more tractable. Many industry problems are “well-behaved” and modern SAT solvers can solve them quickly.

This is a really cool point, no one ever mentioned this to me when I learned about this stuff at university. I wonder though, is there data for this ? Are businesses willing to take the risk and how do they mitigate ?

I'm not sure how popular they are in the wild, but there are a lot of approximation algorithms as well for solving version of these problems that are almost-but-not-quite the same. I wonder if that's just what lots of real-world use cases actually need.

It's kinda obscure that SAT solvers, SMT solvers, and production rules engines (all popular in the old AI) have improved greatly post-2000, almost as much as neural networks.

The wording is a tiny bit misleading because assuming P ≠ NP, then the set of SAT problems that SAT solvers can solve in polynomial time is, by definition, in P and not NP-hard (if they were, then, again, by definition of NP-hard, we could reduce all of the problems in NP to those in that set, proving P = NP, contrary to our assumption). I.e. assuming that there's a subset of SAT that SAT solvers can solve -- of any problem size -- in polynomial time, then that subset is not NP-complete. SAT is still NP-hard (and NP complete), because we can reduce any problem in NP to SAT, but not to that "easy" subset. It's just that the mystery, as Hillel alludes, is that we don't yet know how to classify that subset so it doesn't have a name.

In other words, it's not that NP-complete isn't always hard; assuming P ≠ NP -- it is. It's just that (in addition to obvious subclasses of SAT) there's a non-obvious subclass of SAT that's in P that SAT solvers can solve (again, assuming they actually solve all of the problems in that class in polynomial time) that we have yet to classify, and it is, indeed, an interesting mystery.

I totally agree with this, both the part about having to be clever with the model implementation and how fast and usable it is. For my own research, it ended up that it was a type of set cover problem. To me it felt large, ended up with almost a million non-zero values to optimize (and had to do 10k of them), but the state of the art is so fast. CPLEX optimizes them in like 3 seconds and can tell me that it's provably optimal. Even open source solvers (HiGHS) solves in like 10 seconds

It is true that when I phrased the problem wrong (with multiplication not addition), it was taking forever, and I had to mess around a long time to figure it out. ChatGPT actually sorta helped a little

But it does feel like magic and not used enough. I think Julia JuMP goes a long way towards just expressing the problem easily. It might take more work/tricks to get it to work (big-M tricks are crazy to me) but at least as a first pass if it just works is worth a try, I think

And to be fair, I really wanted it to be provably optimal for the fun of it. But when I set even a 10 minute timelimit, it got a really good solution across the board much faster than I could have found with manual programming

The field of parametric complexity deals with exactly this notion. The idea that some things are NP Hard, but this difficulty only materializes in specific and rare instances, and this does not stop them from being solved for most realistic scenarios.

https://en.m.wikipedia.org/wiki/Parameterized_complexity

There is an interesting result in complexity theory that shows that the obvious greedy algorithm for the minimum set cover problem (add the element that increases your coverage the most, repeat) is essentially the best-possible polynomial time approximation. This sometimes causes people to use the greedy algorithm and think they can't do better.

But this result is about the worst case approximation quality-- the quality on pathological inputs. On ordinary inputs the greedy algorithm by itself is not that great and can easily be outperformed by algorithms with heuristics that anyone can come up with after thinking about the problem for a bit. Heuristics with polynomial complexity just don't improve the worst case performance.

I think this is just a more narrow case of the same underlying error: Taking an interesting yet often rather narrow and academic result and assuming it applies more generally. I suspect it's exacerbated by researchers talking up the significance of their work. I suspect it's also partially a result of the fact that an answer can be surprising and worth study yet still not very useful. The fact that we can say much at all about the space of all possible polynomial time algorithms is very surprising, but it's much more surprising than it is practically useful.

The main points I tell people: Results from complexity theory are usually about best and worst cases, practice usually cares much more about typical cases (which might be application constrained to never be pathological). Results from complexity theory are usually about exact solutions, usually a good approximation is all that we need or it's fine to solve the problem exactly most of the time buy give a bad result in a rare case. Many problems are actually small enough they can be exhaustively checked. Many problems are large enough that only a very rough approximation will ever meet the timing requirements (so just because you have a polytime algorithm it might not help). All these factors mean that while it can be useful to know the limits, they often don't matter.

dnf and zypper are using a SAT solver for package dependency resolution. Here's the information about zypper: https://en.opensuse.org/openSUSE:Libzypp_satsolver

That's a lot of fancy sounding words to say something that is obvious to any programmer. Big O algorithm analysis assumes that input size increases indefinitely. However, in real world problems the input size usually has a natural upper bound. As long as you can write a fast enough implementation (exact or approximate) for the largest conceivable input size, the problem is tractable. All algorithms designed for a bounded input size are technically O(1).

Even reducing it to SAT and invoking a SAT solver is too much. Most of these problems are solvable with simple enumerative recursion with optimizations like memoization, backtracking, and branch-and-bound.

For example, airline computer systems solve NP-Complete problems on a daily basis.

You can also mix problems to change the average complexity.

Take SAT (in NPC) and encode each instance with a word over a binary alphabet (eg. A and B). Then add 2SAT (in POLY) and encode it using an alphabet with four letters (eg. A, B, C and D). If a word has only As and Bs, treat it as SAT, otherwise as 2SAT.

If you chose a random instance of length n (= a sequence of n letters from A to D), the probability it is from SAT (ie contains no C or D) is less than 1/2^n.

Thus most instances are solvable in poly time, and only with neglectable probability you get a "harder" problem from SAT.

Still, this problem is NP complete, as it is in NP and you can trivially reduce SAT to it.

Great article, but:

> "I thought that SAT solvers were widely used in package dependency management. Turns out they’re not!"

Proceeds to link to PubGrub, a "Pub's version solving algorithm, called Pubgrub, solves these issues by adapting state-of-the-art techniques for solving Boolean satisfiability and related difficult search problems."

It's basically a sat solver that uses the problem domain directly. Which they later acknowledge might be a reason for not using an "off the shelf" solver.

It's just funny to present it this way - but I enjoyed the article nontheless.

On the other hand, P isnt't always easy.

The class P is a huge ocean, and so far we have barely scratched the surface of a tiny droplet from that water. This gives us a false impression of comfort, as if a problem was somehow "solved" merely because it belongs to that class. Typical problems in P are not linear nor quadratic, but O(n^k) with k being an humungous constant built of several iterations of Ackerman functions. That P looks "easy" to us is about our lack of imagination and generic examples, not about the class itself.

The same thing applies to undecidable problems. Yes, the halting problem is undecidable in the general case. But most real life programs are expected to always halt, or to repeatedly run a procedure that always halts (event loops, servers).

A trivial way to make sure a program halts is to add an upper bound on how much time it takes to run. A more complex way is using theorem provers. Turing completeness is usually not required for real life programs.

Is the author purposely using the words "hard" and "np-complete" wrong to garner views? Really sours the article

It's easier than in the OP (original post):

Joe is a traveling salesman and has to visit 10 cities, each once. He wants to minimize the driving distance. That is an example of an NP-complete problem. Here NP abbreviated "non-deterministic polynomial" that can use a little explanation (below).

Writing a computer program to solve Joe's problem is easy.

Here in one step more generality: Let the number of cities be the positive integer n. For Joe we had n = 10. Joe has a friend Sam with the same problem, but for Sam n = 1000. Sam's problem is harder than Joe's in the sense that the same computer program will run longer for Sam.

Actually, a computer program that will also do well (explained below) for Sam is also easy to write, should be the same program that did well for Joe.

Now we can get into the "hard" stuff: Joe and Sam are picky and want the minimum distance, down to the last tiny fraction of 1 inch, perfectly so, all the time, including the worst case, no matter where the cities are. Hmm. They want a perfect program.

Here it appears that the running time of the perfect program on the worst case grows like 2^n, exponential growth. Joe and his n = 10 and especially Sam with his n = 1000 would be very happy with growth of the worst case running time like n^k for some positive integer k. That is, the want n^k polynomial running time.

NP? One approach is to be non-deterministic, that is, use a random number generator to pick the cities and maybe get very lucky, and that is so easy to do can do it in polynomial time.

Biggie point: So far no one knows if a program that runs in time n^k is possible.

But, remember, Joe and especially Sam are picky -- they want perfection, the minimum distance down to the last tiny fraction of 1 inch all the time on worst case problems.

Uh, in practice, if are willing to get close on nearly all real problems, we are in quite good shape in practice.

How? For Joe and Sam, one way is to build a minimum spanning tree of the n cities -- there are at least two simple, fast algorithms for that. Then exploit that the cities are in a space with Euclidean distances. Then for the solution, just follow the spanning tree omitting any trips don't have to take. A paper with this solution is old.

It goes on this way: There are lots of problems in combinatorial optimization, all NP-complete, and if have that there is a polynomial algorithm for any one of them then there is for all of them, which is what the "complete" means.

But, e.g., for one of the relatively general (in practical terms of simple problem formulation) NP-complete problems is 0-1 integer linear programming (ILP), can tweak the simplex algorithm of linear programming to do well on nearly all such practical problems. A source of such 0-1 ILP problems is ILP set covering. E.g., I encountered one of those: Consider FedEx and its airplanes, the cities to be served, and the loads to be carried. Each plane leaves Memphis, makes its stops, and returns to Memphis. Call what one plane does a tour. There are lots of candidate tours, but a lot of them can't fly because of scheduled arrival times, limits on loads and distances, etc. So, call the candidate tours that can fly feasible. For each of the feasible tours, find the operating cost. Then the problem is to cover the set of all cities to be served with the feasible tours such that the total cost is minimized. That is an example of 0-1 ILP -- ILP set covering.

0-1 ILP set covering is nice, simple stuff: Get to evaluate the individual tours, or what stands in for those in some other problem, considering lots of really goofy costs and constraints, maybe even some probabilistic stuff where get to take averages, and then do the optimization itself after this initial enumeration work. It's fairly general stuff. Keep it in mind; you might find another application.

The FedEx airplanes are expensive. A good set covering solution should have saved FedEx a lot of money, a significant fraction of their total operating cost otherwise. The FedEx founder liked my lecture on set covering, assigned me to do the work. But the promised stock was late, so I want for a pure/applied math Ph.D.

With such a set covering problem, by doing well, we mean saving a lot of money and/or nearly all the money to be saved even if had a solution that minimized cost down to the last fraction of an inch or dollar or whatever were trying to save. And, nicely enough, often the 0-1 ILP techniques, e.g., some cases of duality, Lagrangian relaxation, etc., can tell when can't save any more than, say, another 1% of the total. One problem I did once, in 0-1 ILP, but not for FedEx, with my solution knew that couldn't save any more than 0.025% more of the total cost. That problem had 40,000 ILP constraints and 600,000 ILP 0-1 variables -- that is, might not be regarded as medium sized and not small and trivial.

So, generally can do well for Joe and even Sam even if the question about NP-complete, polynomial times, minimum cost, and worst case problems is not solved.

Net, in practice, that a problem is in NP-complete, in practice, is nearly always of no concern, in practice. In practice, if save $5 million a day and a perfect solution might save another $100 a day, in practice no one cares, in practice. Did I mention "in practice"? They care a lot about the $5 million and don't want to decline to save the $5 million because there might be $100 more to be saved that they don't know how to save.

By now the techniques of 0-1 ILP and more generally discrete or combinatorial optimization, e.g., in the field operations research or optimization, are old, 50+ years old. There are lots of carefully written, clever books and papers and lots of mature software.

The question of a polynomial algorithm for the NP-complete problems is interesting, curious, one heck of a challenging research problem, maybe a start on some really important work in math and applications of wide variety, maybe a pillar of what is fundamental about computing, etc. But, in practice, for Joe, Sam, Fedex, and more, we've been able to do well for many decades, in practice.

Early in the discovery of NP-complete problems there was a book written at Bell Labs. Bell needed to do network design, and that was discrete optimization. At the start of their book they confessed that they really didn't know how to solve the design problems and then gave a cartoon showing a long list of other people who didn't know either. But by solve they were picky like Joe and Sam -- minimum cost down to the last tiny fraction of the last dollar or penny even on worst case problems.

Since then at least experience shows that their confession and cartoon were way too pessimistic, that for saving the first, say, 99% on essentially all the actual, practical problems was doable. Their attitude was one of the planet's biggest examples, for some work important in practice, of letting the perfect stand in the way of the very good.