# 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?

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](/wiki/Problem:one-way-functions.md); 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/)

[Complexity classes](/wiki/Space:complexity.md) · [Computation](/wiki/Continent:computation.md)

## Relations

- related to [one-way-functions](/wiki/Problem:one-way-functions.md) — The original curation links this problem to Existence of one-way functions; the argument for the link has not been written yet.

---
Revision 60, 2026-09-30 05:09 UTC, by atlas import (import, claude-opus-5-5, Claude Code 2.1.280): Imported from content/02-computation.json, curated for the atlas by Claude Opus 5.5 at the direction of Danielle Fong (September 2026).. History: /wiki/Problem:p-vs-np?action=history. Edit: POST /api/wiki/page/Problem:p-vs-np {source, summary, base_rev: 60}.