Fix the alphabet 0,1, and call a set L⊆0,1^ a language. For x∈0,1^ let |x| denote its length, and let 0,1^≤ m=w∈0,1^: |w|≤ m. Computation is measured on the deterministic multitape Turing machine: a machine M runs in time t(n) if for every input x it halts after at most t(|x|) steps, and M(x)∈0,1 denotes its output. Define mathbfP=Bigl,L⊆0,1^;:;exists a deterministic Turing machine M and constants c,k>0 such that M runs in time c,n^k and bigl(x∈ L iff M(x)=1 bigr) for all x,Bigr, mathbfNP=Bigl,L⊆0,1^;:;exists a polynomial p and V∈mathbfP, V⊆0,1^×0,1^, such that for all x, x∈ L iff exists, w∈0,1^≤ p(|x|) (x,w)∈ V,Bigr, where V∈mathbfP means that the relation V, on suitably paired inputs langle x,w rangle, is decided by a deterministic Turing machine in time polynomial in |x|+|w|. Then mathbfP=mathbfNP.

P versus NP problem

About 55 years old · traced to 1971

Fix the alphabet $\{0,1\}$ , and call a set $L\subseteq\{0,1\}^{*}$ a language. For $x\in\{0,1\}^{*}$ let $|x|$ denote its length, and let $\{0,1\}^{\le m}=\{w\in\{0,1\}^{*}: |w|\le m\}$ .

Computation is measured on the deterministic multitape Turing machine: a machine $M$ runs in time $t(n)$ if for every input $x$ it halts after at most $t(|x|)$ steps, and $M(x)\in\{0,1\}$ denotes its output.

Define

\mathbf{P}=\Bigl\{\,L\subseteq\{0,1\}^{*}\;:\;\exists\ \text{a deterministic Turing machine } M \text{ and constants } c,k>0 \text{ such that } M \text{ runs in time } c\,n^{k} \text{ and } \bigl(x\in L\iff M(x)=1\bigr)\ \text{for all } x\,\Bigr\},

\mathbf{NP}=\Bigl\{\,L\subseteq\{0,1\}^{*}\;:\;\exists\ \text{a polynomial } p \text{ and } V\in\mathbf{P},\ V\subseteq\{0,1\}^{*}\times\{0,1\}^{*},\ \text{such that for all } x,\ \ x\in L\iff \exists\, w\in\{0,1\}^{\le p(|x|)}\ \ (x,w)\in V\,\Bigr\},

where $V\in\mathbf{P}$ means that the relation $V$ , on suitably paired inputs $\langle x,w\rangle$ , is decided by a deterministic Turing machine in time polynomial in $|x|+|w|$ .

Then

\mathbf{P}=\mathbf{NP}.

Equivalent formulations 2Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

P versus NP problem
The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every decision problem for which a proposed positive answer can be quickly verified can also be quickly solved.
source: Wikipedia
The P versus NP conjecture
Let $\bold P$ denote the class of problems solvable in polynomial time, and let $\bold N\bold P$ denote the class of problems whose proposed solutions can be verified in polynomial time.

P versus NP conjecture.
$\bold P\neq\bold N\bold P.$
This is a central question in computational complexity and an algebraic-complexity motivation for geometric complexity theory. It remains open.
source: J. M. Landsberg, “An introduction to geometric complexity theory”, arXiv:1509.02503 (2015).

References

Primary source

Clay Mathematics Institute

Additional references

Stephen Cook, The P versus NP Problem, the official Clay Mathematics Institute problem description.
S. A. Cook, "The complexity of theorem-proving procedures," Proceedings of the Third Annual ACM Symposium on Theory of Computing (1971), 151-158.
R. M. Karp, "Reducibility among combinatorial problems," in Complexity of Computer Computations (1972), 85-103.
T. Baker, J. Gill and R. Solovay, "Relativizations of the P =? NP question," SIAM Journal on Computing 4 (1975), 431-442 — why relativizing techniques cannot settle it.
A. A. Razborov and S. Rudich, "Natural proofs," Journal of Computer and System Sciences 55 (1997), 24-35.
Clay Mathematics Institute, P versus NP problem — the statement above follows it.
Wikipedia, P versus NP problem, the article this problem comes from.

unsolved-problem

InMillennium Prize Problems

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

The problem remains open in accepted mathematics, despite several unverified papers claiming to prove that efficiently checkable problems can all be solved efficiently.

The problem asks whether every problem whose proposed solutions can be checked in polynomial time can also be solved in polynomial time, namely whether $\mathbf{P}=\mathbf{NP}$ . Stephen Cook and Leonid Levin established the foundational theory in 1971; Richard Karp showed in 1972 that many natural problems are $\mathbf{NP}$ -complete.

Known results

$\mathbf{P}\subseteq\mathbf{NP}$ and $\mathbf{NP}$ -completeness (Cook, 1971; Levin, 1973).
Twenty-one natural problems shown $\mathbf{NP}$ -complete (Karp, 1972).
Relativized worlds with both $\mathbf{P}=\mathbf{NP}$ and $\mathbf{P}\ne\mathbf{NP}$ , limiting diagonalization (Baker, Gill, and Solovay, 1975).
Natural-proofs barrier for major circuit-lower-bound strategies (Razborov and Rudich, 1997).

Claimed proofs and June 2026 withdrawal

Several arXiv papers claim to establish $\mathbf{P}\ne\mathbf{NP}$ through circuit or time lower bounds, but the supplied record provides no independent verification. Rami Zaidan’s paper claimed a complete proof, was revised on June 29, 2026, and version $2$ was withdrawn with the record stating that it contains errors, lacks rigor, and is informal.

Current status (as of September 2026): $\mathbf{P}\subseteq\mathbf{NP}$ and the foundational completeness and barrier results are settled, but neither $\mathbf{P}=\mathbf{NP}$ nor $\mathbf{P}\ne\mathbf{NP}$ has an accepted proof; the circulated separation claims remain unverified, with one withdrawn.

Sources

No solutions have been posted yet.

P versus NP problem

The P versus NP conjecture

Primary source

Additional references

Progress summary