Difference between revisions
p-vs-np
Source +0 −0
… 32 unchanged lines
Revision 60 as rendered
Most researchers believe P ≠ NP: that finding is genuinely harder than checking. Three known barriers, relativization, natural proofs and algebrization, rule out whole families of proof techniques, which explains why fifty years of effort have not produced a proof. If P = NP with a practical algorithm, most public-key cryptography would fail and much of mathematics could be automated. The formal-conjectures entry also contains NP ≠ coNP.
Posed 1971, Stephen Cook and Leonid Levin; Gödel asked a version in a 1956 letter to von Neumann.
What would settle it
Lean statement P_ne_NP in formal-conjectures
Prize
$1,000,000 Clay Millennium Prize
Related problems
- The original curation links this problem to Existence of one-way functions; the argument for the link has not been written yet.