6 ms·

P versus NP Explained

80 points by danielrm26 13y ago

VLM 13y 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 13y 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.
- pdpi 13y 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.
  - VLM 13y 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.
    - pdpi 13y ago
      Algorithmic complexity is predicated on what sort of computational model you're working on top of. For the most part, that means "Deterministic Turing Machines", but that's not the only sort of computing machine out there. E.g. quantum computers can solve a whole class of NP problems (like factorisation) in poly time.
lifebeyondfife 13y 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/ http://lifebeyondfife.com/helping/
- prawks 13y 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.
mjn 13y 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 http://www.kmjn.org/notes/nphard_not_always_hard.html
- j2kun 13y 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.
jfasi 13y 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.
- j2kun 13y 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 13y 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 :)
    - j2kun 13y ago
      Tell that to the Quantum Brotherhood. Edit: you may find the head of a cat in your bed, but only if you look and only with probability 1/2.
- deleted 13y ago
  [deleted]
- lifebeyondfife 13y 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.
  - VLM 13y 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.
ithinkso 13y 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.
- danielrm26 13y 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.
  - VLM 13y 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.
peeters 13y 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.
- danielrm26 13y 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.
  - peeters 13y 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?
    - danielrm26 13y ago
      Can I use that?
      - peeters 13y ago
        By all means.
        13y ago
_greim_ 13y 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 13y 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 13y 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_ 13y ago
    Ahh. Thank you. This actually makes more sense than the article itself!
- sherjilozair 13y 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."
jmcgough 13y 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 13y 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.
- mjfl 13y 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 13y ago
    but not every NP-hard problem is in NP
    - mjfl 13y ago
      this is true, see edit
- deleted 13y ago
  [deleted]
jordanlev 13y ago
Why on earth does this web page not display its content when cookies are disabled?
elwell 13y ago
What are some of the ways 'solving' P vs. NP would affect society (or certain specific computing problems)?

80 points by danielrm26 13y ago

VLM 13y 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 13y 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.
pdpi 13y 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.
- VLM 13y 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.
  - pdpi 13y ago
    Algorithmic complexity is predicated on what sort of computational model you're working on top of. For the most part, that means "Deterministic Turing Machines", but that's not the only sort of computing machine out there. E.g. quantum computers can solve a whole class of NP problems (like factorisation) in poly time.

lifebeyondfife 13y 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/ http://lifebeyondfife.com/helping/

prawks 13y 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.

mjn 13y 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 http://www.kmjn.org/notes/nphard_not_always_hard.html

j2kun 13y 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.

jfasi 13y 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.

j2kun 13y 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 13y 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 :)
  - j2kun 13y ago
    Tell that to the Quantum Brotherhood. Edit: you may find the head of a cat in your bed, but only if you look and only with probability 1/2.
deleted 13y ago
[deleted]
lifebeyondfife 13y 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.
- VLM 13y 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.

ithinkso 13y 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.

danielrm26 13y 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.
- VLM 13y 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.

peeters 13y 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.

danielrm26 13y 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.
- peeters 13y 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?
  - danielrm26 13y ago
    Can I use that?
    - peeters 13y ago
      By all means.
      - 13y ago

_greim_ 13y 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 13y 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 13y 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_ 13y ago
  Ahh. Thank you. This actually makes more sense than the article itself!
sherjilozair 13y 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."

jmcgough 13y 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 13y 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.
mjfl 13y 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 13y ago
  but not every NP-hard problem is in NP
  - mjfl 13y ago
    this is true, see edit
deleted 13y ago
[deleted]

jordanlev 13y ago

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

elwell 13y ago

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