P versus NP

Posed in essentially modern form by Cook (1971) and Levin (1973), and anticipated in a 1956 letter from Gödel to von Neumann. Karp's 1972 list of 21 NP-complete problems established that the question is a single question about thousands of problems at once.

Almost every hardness claim in computer science is a conditional statement whose hypothesis is $\mathrm{P} \ne \mathrm{NP}$ or a strengthening of it. A proof of equality with a practical algorithm would break public-key cryptography as currently deployed; a proof of separation would be the first unconditional lower bound of its kind.

• Three known barriers say what a proof cannot look like: relativisation (Baker–Gill–Solovay, 1975), natural proofs (Razborov–Rudich, 1994) and algebrisation (Aaronson–Wigderson, 2008).
• Strong lower bounds are known in restricted models: constant-depth circuits (Håstad), monotone circuits (Razborov), and bounded-depth circuits with counting gates.
• Williams (2011) proved $\mathrm{NEXP} \not\subseteq \mathrm{ACC}^0$ via an algorithmic method, currently the most promising general route.
• The best known general circuit lower bound for an explicit function in NP is roughly $3.1n$, which is not even superlinear in a meaningful sense.