P versus NP Explained

http://www.danielmiessler.com/study/pvsnp/

by danielrm26 • 12 years ago

80 50 12 years ago

VLM5• 12 years ago

Three minor editorial comments:

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.

cousin_it• 12 years ago

most real world problems are either P or small enough scale NP not to matter.

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.

pdpi2• 12 years ago

The article describes P vs NP as the difference between decision/optimisation problems, which doesn't make it seem like what sort of machine you use to solve them has much to do with it at all.

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.

VLM5• 12 years ago

"the fact that you're using a modern computer ... 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.

lifebeyondfife2• 12 years ago

Good concise explanation. For those who missed it a few months back, I wrote a blog post which contained an explanation of NP and, more importantly, why it's important for programmers to recognise NP problems.

The section headings 'Understanding NP-complete completely useless?' and 'Recognising NP-complete problems' are the most relevant. http://lifebeyondfife.com/helping/

prawks• 12 years ago

Cool post, and nice tool! Until now I've kind of been one of those that have been able to identify NP problems and know that "there are ways to optimize them" but haven't had much experience in actually optimizing any in the real world.

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.

mjn2• 12 years ago

A few mild disagreements over interpretation:

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

j2kun3• 12 years ago

A few more (though I love it when people write about one of my favorite topics!)

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.

algorias• 12 years ago

To expand on 2. above: It's a common misconception that the class NP is important because it stands for hard problems, but in fact there are classes of hard problems which we know to be distinct from P. Specifically, P != EXPTIME (see the time hierarchy theorem).

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.

mafribe• 12 years ago

Yes, NP-hardness is a worst-case notion, hence not easy to use in cryptography.

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.

mjn2• 12 years ago

I think it's mostly true that SAT-solvers are better because of decades of research/engineering on them. However there is some speculation that your observation that "you typically lose a lot of structure" is actually sometimes a win, because by "flattening" a representation it might allow some distant implicit constraints to propagate. In planning, for example, that's one hypothesis for where Graphplan and SATplan (two 1990s systems) got their win from, vs. traditional symbolic planners.

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.

jfasi3• 12 years ago

This post explain nothing.

Any article claiming to explain P vs NP without so much as mentioning nondeterministic and deterministic Turing machines is meaningless.

j2kun3• 12 years ago

Not true. You can just use the characterization of NP in terms of certificates and deterministic verifying machines, and still get everything (except maybe the standard proof of the Karp-Lipton theorem).

diminish• 12 years ago

Watch out where you stand. Sons of Turing are a large mafia, which will immediately reduce every other computational construct into TMs and claim you didn't really add up anything :)

lifebeyondfife2• 12 years ago

From a technical standpoint I agree with you - the exact nature of P and NP problem classes should be explained. Here, the initials aren't even defined.

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.

VLM5• 12 years ago

"the subject can appear opaque and irrelevant."

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.

danielrm266• 12 years ago

I strongly disagree. When so many people don't have any idea what the issue is, the most useful resource is something that approaches at THIS level, with links to deeper coverage.

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.

jfasi3• 12 years ago

As innocent as they seem, posts like this are dishonest and dangerous. Imagine you're speaking to someone who actively namedrops papers and impressive concepts, but when you press them further it becomes clear they only skimmed the material and are just repeating these things to seem interesting. Imagine the contempt you'd feel for that person, who willingly puts on a show of intelligence and accepts respect from people who are impressed by their vocabulary, but is actually completely ignorant.

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.

almosnow• 12 years ago

I agree, even without resorting to T. machines you would be able to explain it much better easily. The author really just shows how naive he is about this field, and, salt that with a few cocky phrases like "... many with computer science degrees have a weak understanding of the concept—let alone those without any training on it" and you just get a terrible article.

As expected from HN, upvotes and front page :D!

ithinkso• 12 years ago

I've always enjoyed reading articles about P vs. NP problem but this one missed the point I think. First of all author stated that Unfortunately, many with computer science degrees have a weak understanding of the concept—let alone those without any training on it. but the explanation he gave is actually identical to those that are given in colleges and this is why people have weak understanding of NP problems.

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.

danielrm266• 12 years ago

First of all author stated that Unfortunately, many with computer science degrees have a weak understanding of the concept—let alone those without any training on it. but the explanation he gave is actually identical to those that are given in colleges and this is why people have weak understanding of NP problems.

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.

VLM5• 12 years ago

"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.

peeters4• 12 years ago

The terminology in the text misses the mark a bit.

- 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.

danielrm266• 12 years ago

Apologies. I was trying to keep it as simple as possible. I don't think people who need to know it to that degree will even need the summary I provided.

peeters4• 12 years ago

I think keeping it simple is great, but you should bring your terminology in the text to be consistent with the diagram at the start, otherwise it's confusing.

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?

_greim_2• 12 years ago

P problems are easy for computers to solve, and NP problems are easy for computers to check answers for, but extremely difficult for computers to solve. [...] All P problems are NP problems

Seems like a direct contradiction. Typo, or am I missing something?

tanderson11• 12 years ago

All P problems are in NP. If you can solve a problem in polynomial time, you could simply "check" the problem on an input by solving the problem and seeing if the test input were in the set of solutions. It will clearly take P time to perform that "check" (because you can solve the problem in P time). This means all problem in P must be in NP.

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.

14113• 12 years ago

Sort of - we don't know if NP problems are hard for computers to solve, that's really the whole question!

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.

_greim_2• 12 years ago

Ahh. Thank you. This actually makes more sense than the article itself!

sherjilozair• 12 years ago

If you can solve something easily, then you can also verify its solutions easily.

It is a typo. It should say "but potentially extremely difficult for computers to solve."

peeters4• 12 years ago

This is coming from my suggestion above, but in my suggestion, I omitted "but extremely difficult for computers to solve", leaving it with:

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!)

jmcgough2• 12 years ago

I've heard that if a polynomial-time solution was found for an NP-hard problem, that would mean that all NP-hard problems can be solved in polynomial time. Is this true, and why is that?

random_coder• 12 years ago

It's not true. If a poly-time solution is found for NP-hard problem, then it's not necessarily true that other NP-hard problems can be solved in polynomial time. However, if poly-time solution for an NP-hard implies every NP-complete (and thus every problem in NP) has a polynomial time solution.

mjfl2• 12 years ago

Edit: This might not be true for NP-hard, but I misread your post and assumed you meant NP-complete.

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).

leibniz• 12 years ago

but not every NP-hard problem is in NP

gphilip• 12 years ago

No, this is not true. But the following is true: if a polynomial-time solution was found for an NP-hard problem, that would mean that all problems in the class NP can be solved in polynomial time [1]. This would include all those NP-hard problems which also happen to be in the class NP.

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.

jmcgough2• 12 years ago

Thanks for the explanation - I didn't understood the difference between NP-hard and NP-complete when I asked this (the wiki article on NP-hard helped to clarify!).

jordanlev• 12 years ago

Why on earth does this web page not display its content when cookies are disabled?

elwell• 12 years ago

What are some of the ways 'solving' P vs. NP would affect society (or certain specific computing problems)?

P versus NP Explained

Related Stories