Summary

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