P versus NP: does Boolean satisfiability have a polynomial-time algorithm?

No proof in either direction. Most experts believe $\mathsf{P}\ne\mathsf{NP}$. Three barriers explain why standard techniques fail: relativization (Baker, Gill, Solovay, 1975), natural proofs (Razborov and Rudich, 1994) and algebrization (Aaronson and Wigderson, 2008). The best unconditional results are far weaker: only linear lower bounds on general Boolean circuit size are known for explicit functions in $\mathsf{NP}$, and Williams (2011) proved that $\mathsf{N}\mathsf{E}$ does not have polynomial-size circuits. Geometric complexity theory (Mulmuley and Sohoni) proposes an algebraic-geometric route to related lower bounds, but no separation has come from it. Related time–space progress, such as Williams's 2025 simulation of time in space , concerns versus -type questions, not P versus NP. P versus NP is not among the claims in the batch of AI-generated manuscripts released by OpenAI on 6 October 2026 (Aaronson: "P≠NP isn't there").

If $\mathsf{P}=\mathsf{NP}$ were shown with a practical algorithm, most deployed public-key cryptography would fail, and optimisation, verification, scheduling and machine learning would change at scale; this outcome is considered very unlikely, and a proof of $\mathsf{P}=\mathsf{NP}$ with an impractical algorithm (for example with a huge exponent) would have far less effect. A proof of $\mathsf{P}\ne\mathsf{NP}$ would change no deployed system by itself, since cryptography needs average-case hardness and one-way functions, which does not provide. Its value would be in the techniques (new lower-bound methods) and in settling whether the search for efficient exact algorithms for -complete problems is futile.

A proof of $\mathsf{P}=\mathsf{NP}$ or $\mathsf{P}\ne\mathsf{NP}$ in the standard formalisation above, accepted by the complexity-theory community after scrutiny. The Clay Institute requires publication in a qualifying outlet, at least two years to have passed since publication, and general acceptance in the mathematics community.