# P vs NP

**Type:** Open Problem  
**Domain:** Named Results / Discrete Mathematics  
**Posed:** 1971, Stephen Cook (independently Leonid Levin)  
**Status:** OPEN — Clay Millennium Prize ($1M)  
**Codex URL:** /mathematics/named-results/p-vs-np/  
**Entry status:** Live — v1.0 (2026-05-27)

## Summary
Can every problem whose solution is quickly verifiable also be quickly solved?

## P and NP defined
P: solvable in polynomial time O(n^k). NP: solution verifiable in polynomial time. P⊆NP always; whether P=NP is open.

## NP-completeness
Cook (1971)/Levin: SAT is NP-complete — as hard as every NP problem. Karp (1972): 21 more problems shown NP-complete.

## Why most believe P≠NP
Decades of failed attempts to find fast algorithms for NP-complete problems. But this is consensus, not proof.

## Barriers to proof
Relativisation (Baker-Gill-Solovay 1975), Natural Proofs (Razborov-Rudich 1994) — both show broad classes of techniques cannot resolve the question.

## Cryptography connection
Modern encryption assumes certain NP problems are hard — P=NP would be strong evidence against current security assumptions.

## Sources
### Tier 1
- Cook, S.A. (1971). STOC 1971.
- Karp, R.M. (1972). Complexity of Computer Computations.
### Tier 2
- Fortnow, L. (2009). Communications of the ACM.

---
*Mathematics Codex entry v1.0 — added 2026-05-27 — thecodex.expert/mathematics/*