P versus NP is the most important unsolved problem in computer science and one of the deepest open questions in mathematics. Informally it asks whether every problem whose solution can be checked quickly can also be solved quickly. Almost everyone who works on it believes the answer is no, and nobody has been able to prove it either way.
P is the class of problems a computer can solve in a reasonable amount of time, where reasonable has a precise technical meaning. NP is the class of problems for which a proposed answer can be checked in a reasonable amount of time, whether or not finding that answer is easy.
Checking is often far easier than finding. Verifying that a completed sudoku is valid is quick. Confirming that a given route visits every city under a certain distance is quick. Producing those solutions in the first place, for large instances, appears to be enormously harder. The question is whether that appearance reflects something real or merely reflects our failure so far to find good methods.
In 1971 and 1972 Stephen Cook, Leonid Levin, and Richard Karp established that thousands of apparently unrelated problems are NP-complete, meaning they are the hardest problems in NP and are all equivalent to one another. A fast method for any single one of them would immediately give a fast method for all of them. These problems appear across scheduling, logistics, protein folding, circuit design, and network routing.
If P equals NP, and if the method were practical rather than merely existing in principle, the consequences would be extraordinary. Most modern cryptography rests on the assumption that certain problems are easy to check and hard to solve, and much of it would fail. Optimisation problems across industry would become tractable. Some have argued that mathematical creativity itself would be partly automatable, since finding a proof would become no harder than checking one.
If P does not equal NP, which is the strong majority view among researchers, then a permanent asymmetry exists between recognising a good answer and producing one, and much of computer science is engaged in managing a limit that cannot be removed.
Several proof strategies have been ruled out by results showing that whole categories of argument cannot settle the question, including relativisation, natural proofs, and algebrisation. Each of these results closed off a promising direction and is itself a significant achievement. The problem is one of the seven Millennium Prize Problems, carrying a one million dollar prize, and claimed proofs appear regularly and have so far all failed.
