P versus NP Explained
danielmiessler.com
danielmiessler.com
1. NP-hard problems are not necessarily hard for computers to solve; they are only hard in the worst case, which could be very rare for some NP-hard problems. SAT, for example, is the original canonical NP-complete problem. But in AI, it's nowadays seen as almost a canonical "fast bytecode". Other systems will often want to find a way to reduce their problem to SAT, because that reduction implies tractability, rather than intractability! If you can target SAT in your backend, you can rely on it (probably) being easy to solve, since most instances of SAT can be quickly disposed of by heuristic solvers. (The more common practical problem here is size blow-up in the reduction to SAT, rather than the SAT instance itself being hard to solve.)
2. Partly as a result of #1, the relevance of NP-hardness to cryptography in practice is often overstated. NP-hard problems aren't really hard in the relevant sense: worst-case harness is not sufficient for a one-way function. Attempts to construct one-way functions out of NP-hard primitives have a pretty poor record (not all have been broken, but a number have, and none have caught on). The other direction is true, though, that P=NP would imply no one-way functions.
I wrote a bit more along these lines a while ago: http://www.kmjn.org/notes/nphard_not_always_hard.html
1. There are known algorithms for NP-complete problems that are "faster" than checking all possible solutions (in fact, finding such algorithms have very big implications and make their discoverers very famous). They're just not all that much faster and certainly not polynomial-time, and hence they don't resolve P vs NP. For example, the third problem of finding the largest clique in a graph has the naive algorithm 3^n/3 of checking all solutions, but there is a long line of research improving this, and the fastest known algorithm today is a 2^0.249n algorithm.
2. The question of P vs NP is not the question of whether there are any genuinely difficult problems to solve, if by genuinely difficult we mean no poly-time solution. There are many problems out there that are known to have no polynomial time algorithm. There are even natural problems out there that are known to have no singly exponential time algorithm (i.e. the lower bound is 2^2^n).
3. The traveling salesman example is not correct: the traveller is limited in that he can only visit each city exactly once.
The reason why the P vs NP question is interesting is the possibility of verifying solutions. We know there are easy problems, and we know there are hard problems, but we don't know if there are hard problems that are easy to verify. Intuitively, for many problems it's much easier to recognize a correct solution than come up with one. This is formalized by the statement P != NP, and in that light it's quite clear why the vast majority of researchers believe it to be true.
But, once you know what algorithms and heuristics the SAT solver is using, it's usually not hard to concoct propositional formulae that the prover chokes on. It just happens to be the case that the formulae that humans typically want to get solved are easy for the algorithms we use. Quite why this is nobody really knows.
Also, the reason we typically reduce NP hard-problems to SAT is not that SAT is somehow easier than other NP-hard problems, but because so much effort has been spent on optimising SAT solvers, unlike for almost all other NP-hard problems. As you say, when you reduce a problem to SAT, you typically loose a lot of structure. But the decades of research on SAT solvers more than compensate.
Similar to a question that comes up in compilers, about optimizing high-level vs. low-level representations. High-level representations give you more specific semantic information, but turning everything into a flattened mud of combinator logic or CPS or SSA might allow for some whole-program optimizations that propagate originally-distant constraints.
1) Its not "most real-world challenges" its more like "some easily explainable problems which don't scale very well". Most real world challenges are simple P problems or NP problems on a very small scale. Sample the angular position of all four wheels a thousand times per second, calculate the apparent angular acceleration, cross check with the other wheels, and if its ridiculous, modulate the brakes a hundred times per second. Even if that problem wouldn't scale to 5000 wheeled vehicles, that simply doesn't matter to our 4 wheeled cars, or even 18 wheel semi trucks. Or TLDR most real world problems are either P or small enough scale NP not to matter.
2) "computers being able to quickly solve problems" More like anything being able to solve problems. Classic computer limits are FP multiplier speed, memory limits, stuff like that. This is a problem solving limitation inherent to the class of problem, not a computer technology limitation. A classic Searle Chinese Room emulating a processor, or a single human brain, is just as limited by NP problem solving limitations. Or something along the lines of this problem will not be solved by making a better computer.
3) "Unfortunately, many with computer science degrees" rewrite to "Unfortunately, many computer science degree programs don't require a class in automata theory..."
Please don't overestimate three minor editorial comments; it is a good introductory article.
Isn't that a kind of self-fulfilling prophecy? If we had an efficient way to solve NP-complete problems, they'd be more widely used in the real world.
You can also think of it in terms of those problems that can be solved in poly time, either by deterministic (P) or non-deterministic (NP) Turing machines. From that perspective, the fact that you're using a modern computer, which is effectively a deterministic Turing machine, matters a whole lot.
I'd disagree in that its a math / logic problem not a computer problem. Most of the applications seem to involve a computer or its assumed that if a solution is found it would be applied by computers.
The Pythagorean theorem does not care if its written with chalk or dry erase markers. In a similar way most automata theory proofs don't use or rely upon a computer other than in the word processor and wiki browser sense.
Or maybe another way to say it is the guys who make computers faster at great effort and expense will never make NP problems P just by making faster transistors or putting more transistors on a single die.
The whole topic is not really a computer problems.
- P and NP are not disjoint sets. NP just means "verifiable in polynomial time." There are plenty of easy problems to solve that are verifiable in polynomial time. P is in fact a subset of NP.
- NP-hard problems are ones that are difficult for computers to solve
- NP-complete is the intersection between NP-hard and NP
Furthermore, it presents the P vs NP problem as an attempt by mathematicians to solve P = NP, whereas almost no mathematicians believe P = NP, they're just all trying to prove that P != NP.
I don't think it would be difficult to say something like:
> P and NP are two different kinds of problems. P problems are easy for computers to solve, and NP problems are easy for computers to check answers for. All P problems are NP problems; that is, if it's easy for the computer to solve, it's easy to verify the solution. The P vs NP problem asks: within the class of NP problems, are there problems which are not P, that is, which are not easy for computers to solve?
He then lists three most common examples of NP problems that are not even as close to the real problems as he thinks they are.
This is why the P versus NP problem is so interesting to people. If anyone were to solve it, it would potentially make very difficult problems very easy. and here is where he missed the point completely. This is simply not true - if for example there is polynomial time algorithm solving NP problem then P vs. NP is solved but if this algorithm is lower bounded by, I don't know, n^(10^80) it's not so easy for computers either. It is 'useless' from real software point of view.
The most profound effect of proving that P=NP is that the ability to check any answer's correctness 'fast' (in polynomial time) is sufficient to being able to solve that problem in polynomial time. That's it. Pure theory of computation. No real life super computing boost.
In a computer science class you should be going into the details. This was not designed to do that. It was designed to give a general overview of the concept, as is clearly stated in the beginning.
And I think the latter is more needed than the former. There are plenty of deep explanations of this topic, and very few approachable ones.
I give credit to the author for trying, but having "enjoyed" an automata theory class and having read the textbook there is no "royal road to P/NP" much like geometry. Have to take the entire long road to get to the end.
Analogy time... how would you explain recursion to a general populace without first explaining variables, functions, calling by ref vs value (or just the idea of calling a function at all, and that it returns something), stacks, the concept of procedural programming, the idea of a flowchart, some level of error detection so it doesn't run off into the weeds, some basic ideas about scalability... So Colbert invites you on his show and after the HN cheering dies down he says "I don't know much about computer science, could you explain recursion in plain language in a line or two?" Honestly, I'd probably say "No" or some joke about it being turtles all the way down which the general public wouldn't find very amusing but those who know would laugh.
Recursion is probably the same way. For Colbert purposes you could certainly come up with some glib explanation. When I, or you, or anyone else, have learned recursion we've probably started with that, but then proceeded to build connections with induction, PL semantics, computer architecture, compiler/runtime implementations, and all the other allied topics.
But I do think the earliest, most informal, explanation has its place too, because you have to start somewhere. The learning process is (at least for me) more like proceeding through lots of explanations of the same thing, at greater levels of detail and with different metaphors and external references, than it is like a linear progression from topic to topic.
The section headings 'Understanding NP-complete completely useless?' and 'Recognising NP-complete problems' are the most relevant. http://lifebeyondfife.com/helping/
I enjoyed the explanations of how heuristics and inference fit in to solving those problems, and it was cool to see how little the code needed to change to include those optimizing constraints.
Any article claiming to explain P vs NP without so much as mentioning nondeterministic and deterministic Turing machines is meaningless.
But for coders who've never seen problem classification theory before (not Big O notation), the subject can appear opaque and irrelevant. I'm all for simplified introductions that help those less familiar with formal computer science become more aware of the theoretical side.
I'll give it a shot.
Let me tell you about an onion. One interesting CS topic to google for is Chomsky Hierarchy. You can start out with really simple grammars (rules) and languages (what the rules result in) and advance toward more complicated problems. Amazingly, for no apparent reason, each step contains everything smaller than the step below plus some set of new things that end up equivalent to each other, even if it takes lots of effort to prove it. Like layers on an onion. For example, its mathematically impossible to come up with a math-type regex that can't be solved by a NFA and impossible to come up with a NFA that can't be solved by a DFA, and all those equivalent regular languages live inside a bigger class of CFLs and PDAs and so on, bigger and more complex every stage you go up. Its all very complicated and highly developed and pretty much figured out at the lower and mid levels. Turing machines seem to be the king of the hill at the somewhat mysterious top. So, thats enough talk about the shape on an onion.
Deep in the onion, there exists one terribly complicated set of vaguely equivalent problems that Turing machines can solve, which scale horribly as the size of the problem increases. And then there is a competing set of problems that scale really easily and are quickly solved. Inside the families they are all cousins of each other and never marry outside their families, ever. So if you find a way to quickly solve one NP its been proven you can warp that technique into solving another NP problem, more or less. But it never, ever, so far, hops between families. NP problems and P problems just don't procreate together, sorta. Its just like when you slice open an onion and find two independent sprouts that have nothing to do with each other. Why, I donno. Nobody knows why. At least WRT P=NP, donno about the onions.
Now its time for idle speculation. How do these apparently separate families fit in the Chomsky Hierarchy, could there be another separate layer of NP problems above the P problems and a matching layer of NP "machines" vs P "turing machines"? Is there a layer on top where if you take a turing machine and add magic pixie dust now it can solve NP problems in P time? If P=NP so this disjoint set of problems is just equivalent Turing solvable problems, how come nobody has proven it yet despite enormous effort and motivation? How come languages that apparently have nothing to do with each other like REGEX and DFA are mathematically proven the same but nobodies proven it yet for P = NP, doesn't that imply its incredibly unlikely they are the same because all the other levels "intermingle" their languages with each other? How does quantum computing fit in, if it does at all in any way?
I tried hard to shove P=NP and the Chomsky hierarchy together, its not going to be insightful to point out that I really swung a sledgehammer to slam this connector into that socket; I already know that. Also I simplified some stuff (well, OK, I simplified everything). But its hopefully an entertaining read and not entirely irrelevant and opaque.
You just proved the point. I'm going to read what you wrote, but most people will not.
The point of my resource was to approachable and consumable within seconds.
None the less, in the spirit of XKCDs "Up Goer Five" I present:
The Crying Onion of P probably does not equal NP.
Computer innards are layered like onions. Just like an onion, bigger computer innard layers contain all of the smaller less complicated layers inside them. There are lots of layers, some much better understood than others. Everything in one layer is the same as everything else in its layer even if at first glance it looks very different. One possible exception is the most difficult layer of the computer innard onion might be split into two layers P and NP. Smart people have worked very hard for many years but are not sure if the layers are split or not. The onion of P probably does not equal NP is so complicated it makes people cry, just like an onion.
And in the proud tradition of the previously mentioned XKCD comic, "Lots of fire comes out here"
Some things aren't consumable in seconds. You either put in the effort to learn something properly, or you don't and content yourself with not knowing.
If you dive super deep you don't have a summary in plain language, you have a competing explanation.
There are already a million of those; this isn't that.
Now imagine you're speaking to someone who read this post. That person is just as ignorant as our big-mouthed friend, but they don't even know it. They read some post, learn a new term or two, and go out into the world not knowing that what they just read contains no real knowledge whatsoever. A post like this does a huge disservice to that person, because not only does it leads them into ignorance, it actually makes them less empowered to rise above it.
As expected from HN, upvotes and front page :D!
Seems like a direct contradiction. Typo, or am I missing something?
The error is that not all problems in NP are "extremely difficult for computers to solve". The difficulty of solving problems in NP varies drastically between particular problems.
Technically, P is a subset of NP. Problems in NP have answers (called certificates) which can be verified, or checked, using an algorithm that runs in polynomial time (that is asymptotically O(n^x), where X is a finite integer). Problems that are in P are those that have a polynomial time algorithm to construct an answer.
Any problem that's in P is therefore in NP, as we can simply run the algorithm for constructing the answer then compare it with the certificate to see if they match.
P vs NP simply asks if all problems in NP can be solved in polynomial time, hence P=NP.
It is a typo. It should say "but potentially extremely difficult for computers to solve."
> P problems are easy for computers to solve, and NP problems are easy for computers to check answers for.
The problem is the text still uses "NP problems" and "NP complete problems" interchangeably, when it shouldn't. (The diagram at the top gets it right!)
Yes. It is because every problem in NP can be "reduced" (transformed into) an NP-complete problem in polynomial time. Therefore if a polynomial time solution for an NP-complete problem exists, the algorithm:
Have problem: 1) Transform problem into NP-complete problem (polynomial time) 2) Solve NP-complete problem (polynomial time)
Two polynomial time steps make a polynomial time algorithm.
The proof that every problem in NP is polynomial-time reducible to an NP-complete problem is pretty long and complicated, involving the formalism of Turing Machines, but it can be found in most textbooks on the theory of computation and I believe it is called the Cook-Levin Theorem (that proves the 3SAT is NP-complete, and then most other theorems show that 3SAT is reducible to them).
NP-hard can be read as "as hard to solve as any problem in the class NP". So if we can solve one of these hard problems in polynomial time, then -- by the meaning of NP-hard -- we can solve all problems in the class NP in polynomial time.
The reason why your statement is not true as it is, is that there are NP-hard problems which are not inside the class NP. These problems are "much harder than" any problem in the class NP and so, being able to solve all problems in NP in polynomial time does not mean that these "harder than all of NP" problems can also be solved in polynomial time. Check the Wikipedia entry on NP-hard for an example of such a "harder-than NP, but also NP-hard" problem. https://en.wikipedia.org/wiki/NP-hard
A problem which is both (i) NP-hard, and (ii) in NP is said to be NP-complete. If a polynomial-time solution was found for an NP-hard problem, that would mean that all NP-complete problems can be solved in polynomial time (because they are all in NP).
[1] There is a fine point here turning on what "can be solved" means. If we take "can be solved" to mean "there exists an algorithm", then this statement is fine. Otherwise ... but that is an arcane point anyway.