“P versus NP” is more than just an abstract mathematical puzzle. <br />
It seeks to determine–once and for all–which kinds of problems can be solved by computers, and which kinds cannot. <br />
As you are probably aware, “P”-class problems are “easy” for computers to solve; that is, solutions to these problems can be computed in a reasonable amount of time compared to the complexity of the problem. <br />
Meanwhile, for “NP” problems, a solution might be very hard to find–perhaps requiring billions of years’ worth of computation–but once found, it is easily checked. (Imagine a jigsaw puzzle: finding the right arrangement of pieces is difficult, but you can tell when the puzzle is finished correctly just by looking at it.)<br />
NP-class problems include many pattern-matching and optimization problems that are of great practical interest, such as determining the optimal arrangement of transistors on a silicon chip, developing accurate financial-forecasting models, or analyzing protein-folding behavior in a cell.<br />
The “P versus NP problem” asks whether these two classes are actually identical; that is, whether every NP problem is also a P problem. If P equals NP, every NP problem would contain a hidden shortcut, allowing computers to quickly find perfect solutions to them. But if P does not equal NP, then no such shortcuts exist, and computers’ problem-solving powers will remain fundamentally and permanently limited. Practical experience overwhelmingly suggests that P does not equal NP. But until someone provides a sound mathematical proof, the validity of the assumption remains open to question.<br />
Even if Deolalikar’s proof were found to be sound, then the question remains–what impact would such a proof have on relevant areas of computing?<br />
Superficially, one might think the answer is “not much.” “Proving that P does not equal NP would just confirm what almost everyone already assumes to be true for practical purposes,” explains Scott Aaronson, a complexity researcher at MIT’s Computer Science and Artificial Intelligence Laboratory.
Thank you, Ms. Fractal, for selecting my reply as best answer to your P=NP problem. Much appreciated. Cheers, ABC
Why of course! That was precisely what I meant by discussing the example of a jigsaw puzzle that one's brain can integrate the information and tell whether or not a completed puzzle was put together correctly.
That's not really what it's about though. It isn't a question of whether or not the solution can be extrapolated. Instead it deals with how the complexity of the problem affects the time to compute vs the time to verify.
The best way to think about it is cracking data encryption using brute force. The actual problems being used to prove the issue one way or the other are rigidly formalized and incredibly complex but this is a fairly simple real-world application. I'm also not concerned with specific technical details and use this only as a theoretical example of the central issue.
So starting with an encryption key consisting of 5 characters there are a certain number of possible permutations and each one is individually checked until the correct key is found.
Adding an additional character to the key results in a linear increase in computing time to verify the answer because each additional character increased the time needed to verify the answer the same amount the same amount. So the solution is calculated in polynomial time by multiplying the number of digits by the time needed to verify each digit.
But because each additional digit increases the number of possible solutions exponentially the time needed to find the solution also increases exponentially. That is the essence of whether P can equal NP. In order for them to be equal both the time needed to find the solution (P) and to verify it (NP) could be expressed as polynomial functions.
No one has yet found a way to do that, which the heart of the P=NP debate. These is no known algorithm that can solve problems with exponentially increasing complexity without also requiring an exponentially increasing amount of time. Possible solutions do exist for a quantum computer though. But until we get bits that can be 0 and 1 at the same time I just don't see it being possible for P to equal NP.
We're talking analogy, people.