“P versus NP” is more than just an abstract mathematical puzzle. <br />

<br />

It seeks to determine–once and for all–which kinds of problems can be solved by computers, and which kinds cannot. <br />

<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 />

<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 />

<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 />

<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 />

<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 />

<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.