Problems with a quick solution are said to be "P". Problems without a quick solution, but with a quick way of checking a solution are said to be "NP". The question is this: If a problem can have a solution checked quickly, does that imply that it can be solved quickly?
Although it sounds like the answer is obviously "no," proving that has been shown to be hard, and the proof has become increasingly important.
(Yes, there are proofs that finding proofs is hard)
=====
Now for more detail:
Consider the problem of graph three coloring. I give you a bunch of points, some connected by lines, and three crayons. Your task is to color the points so that any line gets different colors at its ends.
If you claim you've done it then it's trivial for me to check, I jsut look at (at most) each line and check its ends. That takes time proportional to the number of edges, which is at most N^2 where N is the number of points.
It takes time proportional to a polynomial in the size of the example you're working on.
Such a problem where checking an alleged solution takes polynomial time is called "NP".
Consider the question of factoring an integer into its prime components. I give you 693, you give me { 3, 3, 7, 11 }. Now I can check if you're right in just polynomial time, but currently there is no known polynomial time algorithm to accomplish the factoring.
RSA depends on this.
Now some problems can be solved in polynomial time. The challenges of "Multiply these two numbers" or "Decide if this graph can be 2-colored" are both examples. Such problems are said to be in P, the collection of all problems whose solutions are polynomial time in the size of the instance.
Some problems do have a polynomial time method for checking an alleged solution. Such problems are said to be in NP.
Currenty there are problems for which there is currently no known polynomial time solution, but which are in NP. The question is whether we are just no yet clever enough to find a polynomial algorithm, or whether these problems genuinely do not have any polynomial algorithm.
If there is an as yet unknown algorithm for solving an NP problem in polynomial time, then that problem gets put into P. The sensible question to ask is this:
Do we have to check every NP problem?
The answer is a very, very clever- No.
In 1971 Stephen Cook showed that any problem that was NP could be converted to an instance of 3-SAT in a relatively efficient manner, in such a way that a solution to the 3-SAT instance could then be converted back to a solution of the original instance. In some very real sense 3-SAT (which is NP) is at elast as hard, if not harder, than any NP problem.
If you can solve 3-SAT, you can (in principle) solve every NP problem with only polynomial time extra work.
So 3-SAT has been called "NP-Complete" - solving it would completely solve the NP class of problems.
Since then thousands of problems have been shown to be NPC, including 3-coloring, travelling salesman (TSP), knapsack, and many more.
Many attempts have been made to construct public-key encryption systems based on problems known to be NPC, but it always seems that adding the necessary trap-door reduces the difficulty of the problem to sub-NPC. RSA and Diffie-Hellman-Merkle-Williamson key negotiation rely on the difficulty of factoring and discrete logarithms respectively, but these are known (or believed - not sure of the current state) to be sub-NPC.
So the question is this:
Are problems in NPC outside of P, or are they in P?
Is 3-SAT or 3-coloring solvable in polynomial time or not?
The paper that's circulating now says that 3-SAT cannot be solved in polynomial time.
Other results in the field show that the result would be surprising. All of the above can be made relative to an Oracle, and when that's done the proof that P is or is not NP becomes impossible. Or at least harder. Or something.
That's where the details start to matter. I hope I've given enough context for you to start to read the more serious stuff, and haven't said anything wildly wrong.
> Many attempts have been made to construct public-key encryption systems based on problems known to be NPC, but it always seems that adding the necessary trap-door reduces the difficulty of the problem to sub-NPC. RSA and Diffie-Hellman-Merkle-Williamson key negotiation rely on the difficulty of factoring and discrete logarithms respectively, but these are known (or believed - not sure of the current state) to be sub-NPC.
A clarification here is that these rely upon the existence of one way functions, of which discrete logarithms and factoring are conjectured to be in. A proof of the existence of one way functions is actually a slightly stronger result than P!=NP (as it relates to languages with only a single accepting state rather than many. The name of the class escapes me and Complexity Zoo is unresponsive at the moment)
So if P = NP, that would be a problem for RSA as in theory there would be a quick way of factoring your big number (even if no-one has yet discovered how to do it). With P != NP encryptors can sleep soundly?
Quick meta question. Is this OK? I think a thread like this pointing to a Wikipedia article is kind of lousy, for three reasons:
- We have a huge P!=NP thread on the front page. If people need a primer or want to discuss the problem, shouldn't the comments be in there? It's nice to have it in one place, right? For example, I'm sure that RiderOfGiraffes's writeup would be well received in that thread.
- Since this issue is front and center, what's the point of the link at all? Surely anyone who wants context on P=NP can figure out how to find the Wikipedia article. This isn't like the occasional Wikipedia link that's meant to highlight some interesting obscurity.
- It's sure lazy. If you want to educate people, then why not find a nice introduction to the topic that they wouldn't have come across on their own? Or write one.
Why would you be afraid to ask about something? Unless it's a trivial question that can be easily googled, asking questions is nothing to be afraid of.
Worst case someone will downvote or ridicule you. But the expected value of asking good questions in high quality communities is positive.
The JACM frequently receives submissions purporting to solve a long-standing open problem in complexity theory, such as the P/NP problem. Such submissions tax the voluntary editorial and peer-reviewing resources used by the JACM, by requiring the review process to identify the errors in them. The JACM remains open to the possibility of eventual resolution of P/NP and related questions, and continues to welcome submissions on the subject. However, to mitigate the burden of repeated resubmissions of incremental corrections of errors identified during editorial review, the JACM has adopted the following policy:
*No author may submit more than one paper on the P/NP or related long-standing questions in complexity theory in any 24 month period, except by invitation of the Editor-in-Chief. This applies to resubmissions of previously rejected manuscripts.
(P=!NP would allow easily creating a problem which God himself cannot solve, making omnipotence impossible. Science is not allowed to prove/disprove the exitance of God per definition, thus P must be equal to NP, where even a non-constructive proof would allow for a God.)"
I wonder what kind of education leads to statements like this.
Can somebody explain to me why articles on complexity are careless with the term "Traveling Salesman Problem" (TSP)?
To me, TSP means "find the shortest route visiting these cities once". That is not a problem that's in NP, since there's no way to verify the solution (shortest route) in polynomial time. Am I right?
What people typically mean is the decision version of TSP: "Find a route visiting all these cities that in less than X total distance cost". That's in NP, of course, since I can quickly check (a) the route connectedness (b) whether the route visits all cities once (c) the total cost of the route is below X.
Do I have my terminology wrong, or are people writing about a very formal territory so unusually careless with terminilogy?
[+] [-] RiderOfGiraffes|15 years ago|reply
Problems with a quick solution are said to be "P". Problems without a quick solution, but with a quick way of checking a solution are said to be "NP". The question is this: If a problem can have a solution checked quickly, does that imply that it can be solved quickly?
Although it sounds like the answer is obviously "no," proving that has been shown to be hard, and the proof has become increasingly important.
(Yes, there are proofs that finding proofs is hard)
=====
Now for more detail:
Consider the problem of graph three coloring. I give you a bunch of points, some connected by lines, and three crayons. Your task is to color the points so that any line gets different colors at its ends.
If you claim you've done it then it's trivial for me to check, I jsut look at (at most) each line and check its ends. That takes time proportional to the number of edges, which is at most N^2 where N is the number of points.
It takes time proportional to a polynomial in the size of the example you're working on.
Such a problem where checking an alleged solution takes polynomial time is called "NP".
Consider the question of factoring an integer into its prime components. I give you 693, you give me { 3, 3, 7, 11 }. Now I can check if you're right in just polynomial time, but currently there is no known polynomial time algorithm to accomplish the factoring.
RSA depends on this.
Now some problems can be solved in polynomial time. The challenges of "Multiply these two numbers" or "Decide if this graph can be 2-colored" are both examples. Such problems are said to be in P, the collection of all problems whose solutions are polynomial time in the size of the instance.
Some problems do have a polynomial time method for checking an alleged solution. Such problems are said to be in NP.
Currenty there are problems for which there is currently no known polynomial time solution, but which are in NP. The question is whether we are just no yet clever enough to find a polynomial algorithm, or whether these problems genuinely do not have any polynomial algorithm.
If there is an as yet unknown algorithm for solving an NP problem in polynomial time, then that problem gets put into P. The sensible question to ask is this:
Do we have to check every NP problem?
The answer is a very, very clever- No.
In 1971 Stephen Cook showed that any problem that was NP could be converted to an instance of 3-SAT in a relatively efficient manner, in such a way that a solution to the 3-SAT instance could then be converted back to a solution of the original instance. In some very real sense 3-SAT (which is NP) is at elast as hard, if not harder, than any NP problem.
If you can solve 3-SAT, you can (in principle) solve every NP problem with only polynomial time extra work.
So 3-SAT has been called "NP-Complete" - solving it would completely solve the NP class of problems.
Since then thousands of problems have been shown to be NPC, including 3-coloring, travelling salesman (TSP), knapsack, and many more.
Many attempts have been made to construct public-key encryption systems based on problems known to be NPC, but it always seems that adding the necessary trap-door reduces the difficulty of the problem to sub-NPC. RSA and Diffie-Hellman-Merkle-Williamson key negotiation rely on the difficulty of factoring and discrete logarithms respectively, but these are known (or believed - not sure of the current state) to be sub-NPC.
So the question is this:
Are problems in NPC outside of P, or are they in P?
Is 3-SAT or 3-coloring solvable in polynomial time or not?
The paper that's circulating now says that 3-SAT cannot be solved in polynomial time.
Other results in the field show that the result would be surprising. All of the above can be made relative to an Oracle, and when that's done the proof that P is or is not NP becomes impossible. Or at least harder. Or something.
That's where the details start to matter. I hope I've given enough context for you to start to read the more serious stuff, and haven't said anything wildly wrong.
References:
http://en.wikipedia.org/wiki/NP-complete
http://en.wikipedia.org/wiki/NP_(complexity)
http://en.wikipedia.org/wiki/P_versus_NP_problem#Results_abo...
http://www.solipsys.co.uk/new/PVsNP.html?HN
[+] [-] vmind|15 years ago|reply
A clarification here is that these rely upon the existence of one way functions, of which discrete logarithms and factoring are conjectured to be in. A proof of the existence of one way functions is actually a slightly stronger result than P!=NP (as it relates to languages with only a single accepting state rather than many. The name of the class escapes me and Complexity Zoo is unresponsive at the moment)
[+] [-] retube|15 years ago|reply
[+] [-] mquander|15 years ago|reply
- We have a huge P!=NP thread on the front page. If people need a primer or want to discuss the problem, shouldn't the comments be in there? It's nice to have it in one place, right? For example, I'm sure that RiderOfGiraffes's writeup would be well received in that thread.
- Since this issue is front and center, what's the point of the link at all? Surely anyone who wants context on P=NP can figure out how to find the Wikipedia article. This isn't like the occasional Wikipedia link that's meant to highlight some interesting obscurity.
- It's sure lazy. If you want to educate people, then why not find a nice introduction to the topic that they wouldn't have come across on their own? Or write one.
[+] [-] Terretta|15 years ago|reply
1. HackerNews is our personal Google, Wikipedia, and blog host rolled into one.
2. By putting the rest of the Internet here, we may never have to leave this site.
3. By only needing one site, we can finally reclaim the browser URL bar for a little more comment space.
[+] [-] drx|15 years ago|reply
Worst case someone will downvote or ridicule you. But the expected value of asking good questions in high quality communities is positive.
[+] [-] yarapavan|15 years ago|reply
The JACM frequently receives submissions purporting to solve a long-standing open problem in complexity theory, such as the P/NP problem. Such submissions tax the voluntary editorial and peer-reviewing resources used by the JACM, by requiring the review process to identify the errors in them. The JACM remains open to the possibility of eventual resolution of P/NP and related questions, and continues to welcome submissions on the subject. However, to mitigate the burden of repeated resubmissions of incremental corrections of errors identified during editorial review, the JACM has adopted the following policy:
*No author may submit more than one paper on the P/NP or related long-standing questions in complexity theory in any 24 month period, except by invitation of the Editor-in-Chief. This applies to resubmissions of previously rejected manuscripts.
Link:http://jacm.acm.org/instructions/pnp
[+] [-] jordyhoyt|15 years ago|reply
"1., If P not equal NP, then God cannot exist.
(P=!NP would allow easily creating a problem which God himself cannot solve, making omnipotence impossible. Science is not allowed to prove/disprove the exitance of God per definition, thus P must be equal to NP, where even a non-constructive proof would allow for a God.)"
I wonder what kind of education leads to statements like this.
[+] [-] wlievens|15 years ago|reply
[+] [-] alanstorm|15 years ago|reply
[+] [-] wlievens|15 years ago|reply
To me, TSP means "find the shortest route visiting these cities once". That is not a problem that's in NP, since there's no way to verify the solution (shortest route) in polynomial time. Am I right?
What people typically mean is the decision version of TSP: "Find a route visiting all these cities that in less than X total distance cost". That's in NP, of course, since I can quickly check (a) the route connectedness (b) whether the route visits all cities once (c) the total cost of the route is below X.
Do I have my terminology wrong, or are people writing about a very formal territory so unusually careless with terminilogy?