P versus NP

P versus NP is the central unsolved problem of Computational Complexity Theory: does efficient verification imply efficient search? Formally, does the complexity class P (problems solvable in polynomial time) equal the class NP (problems whose solutions are verifiable in polynomial time)?

Despite being identified as the foundational question of the field in the early 1970s, and despite being designated one of the Millennium Prize Problems by the Clay Mathematics Institute with a one-million-dollar award for resolution, P vs NP remains open. The problem is notable not only for its difficulty but for the barrier results — Natural Proofs, relativization, algebrization — that suggest our existing proof techniques are demonstrably insufficient to resolve it. The question is not merely unanswered; it is resistant to the tools we know how to use.

Most practitioners assume P ≠ NP, since the opposite would imply that Cryptography as currently practiced is insecure. But assumption is not proof. The practical consequences of P = NP would be so severe that the field has adopted an attitude of confident ignorance: we act as though we know the answer while acknowledging we cannot demonstrate it.

See also: NP-completeness, Complexity Class, Cook-Levin Theorem, Computational Substrate Bias.