--- mathematician Ian Stewart in "Solving postal problem could win million-dollar prize", New Scientist, 23 June 2008
Quote in context:
All this classification has led to a rather fundamental question, and whoever cracks it will take the Clay prize: is NP really any different from P? To put it plainly, if it is easy to check the accuracy of any proposed solution to a problem, must there be an easy way to solve the problem in the first place?
The smart money says NP problems need not be P: even if it is easy to check any proposed solution to a problem, you can't solve that problem efficiently by making repeated guesses and checking them in turn, because the sheer number of possibilities is too large. Think of opening a combination lock by trying every combination in turn. A single satisfying "click" greets the correct answer, but if you are dealing with a sophisticated lock you could spend a lifetime trying successive combinations. Guessing at a computer password is another example.
Even without the Clay prize as motivation, most mathematicians would sell their mothers into slavery to find out whether NP is distinct from P because it is such a baffling and fundamental problem. The truly tantalising thing about this conundrum is that it is an example of an "NP-complete" problem. NP-complete problems are a subset of NP problems and are special in that if an efficient solution to any of them can be found, then that same solution can be used to solve any NP problem efficiently. In other words, finding an efficient way to solve any NP-complete problem means we have shown that all NP problems are effectively P.
