P versus NP

P versus NP is the most famous open question in computer science, and one of the great unsolved problems of mathematics. In one sentence: if a solution to a problem is easy to CHECK, must the problem also be easy to SOLVE? P is the class of problems we can solve quickly; NP is the class we can check quickly. The question asks whether these two classes are actually the same. Almost everyone believes they are not, but nobody has proven it.

Precisely, P is the set of decision problems solvable by a deterministic algorithm in polynomial time, and NP is the set verifiable in polynomial time given a certificate. We know for sure that P is contained in NP. The open question is whether the reverse holds: is NP contained in P, so that P = NP? Because the NP-complete problems are the hardest in NP and all interreducible, the question collapses to a single test: if even ONE NP-complete problem (say SAT) has a polynomial-time algorithm, then P = NP and every NP problem becomes tractable; if even one provably needs super-polynomial time, then P is not equal to NP. No such algorithm and no such lower bound has ever been found.

The stakes are enormous and concrete. If P = NP, then problems that today look hopeless, optimal scheduling, automatic theorem proving, breaking much of modern cryptography, would all become efficiently solvable, which is one reason most researchers expect P is not equal to NP, since so much of secure computing relies on certain problems being hard. It is one of the seven Clay Mathematics Institute Millennium Prize Problems, carrying a one-million-dollar reward. Be careful about what a resolution means: a proof that P is not equal to NP would confirm a barrier we already assume, while a constructive proof that P = NP could upend cryptography overnight, though a non-constructive proof might change little in practice.