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)
Just to answer your query here: integer factorization is still suspected to be outside of P, NP-complete and co-NP-complete (recently some have hinted that it may in fact be NP-complete, I cannot track the link to the email discussion atm). No proof for either of those claims exists yet.
Discrete logarithm has been found to be in BQP (Shor's algorithm), and therefore not NP-complete, since BQP is suspected to be disjoint from NP-complete. No proof of this claim is available, either.
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?
No, not really. P != NP should be read: It is not true that for every NP, there is a P, but for any specific P problem, there MAY be an NP solution unless you can prove otherwise.
This is a classic syllogism: All tigers are cats, but not all cats are tigers.
Similarly, if P != NP, you can say, there absolutely, and provably, are solutions which are hard to solve, but easy to validate. However, this fact alone does not tell you if your problem is that way.
If P=NP were true, you could consider every public-key cryptographic system to be a ticking time-bomb. It's only a matter of time before someone find's the easy solution that breaks the entire system irrevocably, because such a solution absolutely does exist if P=NP.
P != NP is status quo. It means: Breathe easy, folks. Your cryptography systems may not be provably secure, but they are certainly not provably unsecure as a category.
As you might expect, it's not as simple as that. There are caveats about the degree of the polynomial (n^1000 is pretty fast growing) and we'e pretty sure factoring isn't in NPC anyway.
But if P==NP then there is a polynomial factoring algorithm that we haven't yet found, and that would probably be bad for current public-key crypto.
The current result seems to say that P!=NP, so at least it's still plausible, even likely, that there's no polynomial factoring algorithm.
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