P vs NP
Asks whether every efficiently verifiable solution can also be efficiently found.
The P vs NP problem asks whether the class P of problems solvable in polynomial time equals the class NP of problems whose solutions can be verified in polynomial time. A resolution either way would have profound consequences: P = NP would imply that every search problem with efficiently checkable solutions is itself efficiently solvable, upending modern cryptography and optimization. The consensus among experts strongly favors P != NP, but three major proof barriers -- relativization (Baker-Gill-Solovay, 1975), natural proofs (Razborov-Rudich, 1994), and algebrization (Aaronson-Wigderson, 2008) -- show that any valid proof must use fundamentally new techniques.
Formula
Can every problem whose solution is efficiently verifiable also be efficiently solved? The central open question in theoretical CS.
Boolean satisfiability is NP-complete: every NP problem reduces to it in polynomial time (Cook 1971, Levin 1973).
If P = NP, most modern cryptography collapses — factoring, discrete log, and lattice problems all become easy.
Summary
The P vs NP problem asks whether the class P of problems solvable in polynomial time equals the class NP of problems whose solutions can be verified in polynomial time. A resolution either way would have profound consequences: P = NP would imply that every search problem with efficiently checkable solutions is itself efficiently solvable, upending modern cryptography and optimization. The consensus among experts strongly favors P != NP, but three major proof barriers -- relativization (Baker-Gill-Solovay, 1975), natural proofs (Razborov-Rudich, 1994), and algebrization (Aaronson-Wigderson, 2008) -- show that any valid proof must use fundamentally new techniques.
