Difference between revisions
p-vs-np
Status and infobox
- status:
—→ open - kind:
—→ problem - year:
—→ 1971 - statement:
—→ Can every problem whose solutions can be checked quickly also be solved quickly?
Relations
- + related to one-way-functions: The original curation links this problem to Existence of one-way functions; the argument for the link has not been written yet.
Source +31 −0
+---
+title: P versus NP
+kind: problem
+status: open
+year: 1971
+authors: Stephen Cook and Leonid Levin; Gödel asked a version in a 1956 letter to von Neumann
+statement: Can every problem whose solutions can be checked quickly also be solved quickly?
+space: complexity
+---
+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 [[related::Problem:one-way-functions|Existence of one-way functions]]; the argument for the link has not been written yet.
+
+## Sources
+
+- [Wikipedia: P versus NP problem](https://en.wikipedia.org/wiki/P_versus_NP_problem)
+- [Clay Mathematics Institute](https://www.claymath.org/millennium/p-vs-np/)
+
+[[Space:complexity|Complexity classes]] · [[Continent:computation|Computation]]
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.