← All problems

P versus NP problem

55 years old · traced to

Let Σ\Sigma be a finite alphabet with at least two symbols and let Σ∗\Sigma^* be the set of finite strings over Σ\Sigma. A language is a subset L⊆Σ∗L\subseteq\Sigma^*. For a deterministic Turing machine MM with input alphabet Σ\Sigma, let L(M)L(M) be the set of strings ww on which MM halts in its accepting state, and let tM(w)∈N∪{∞}t_M(w)\in\mathbb N\cup\{\infty\} be the number of steps of MM on input ww. The worst-case running time is

TM(n)=max⁡{tM(w):w∈Σn}.T_M(n)=\max\{t_M(w): w\in\Sigma^n\}.

MM runs in polynomial time if there is k∈Nk\in\mathbb N with TM(n)≤nk+kT_M(n)\le n^k+k for all nn.

  • P\mathbf P is the class of languages L(M)L(M) for Turing machines MM that run in polynomial time.
  • A checking relation is a relation R⊆Σ∗×Σ1∗R\subseteq\Sigma^*\times\Sigma_1^* for some finite alphabet Σ1\Sigma_1. It is polynomial-time if the language {w#y:R(w,y)}\{w\#y: R(w,y)\} lies in P\mathbf P, where #\# is a new symbol.
  • NP\mathbf{NP} is the class of languages L⊆Σ∗L\subseteq\Sigma^* for which there are k∈Nk\in\mathbb N and a polynomial-time checking relation RR such that, for every w∈Σ∗w\in\Sigma^*,
w∈L  ⟺  ∃ y (∣y∣≤∣w∣k and R(w,y)).w\in L\iff\exists\,y\ \bigl(|y|\le|w|^k\ \text{and}\ R(w,y)\bigr).

Every language in P\mathbf P is in NP\mathbf{NP}, so P⊆NP\mathbf P\subseteq\mathbf{NP}.

Problem. Determine whether

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

This is the formulation in Cook's official Clay problem description [1]. The answer does not depend on the choice of alphabet with ∣Σ∣≥2|\Sigma|\ge2, and the class P\mathbf P is the same for all standard deterministic machine models. A solution is a proof of either P=NP\mathbf P=\mathbf{NP} or P≠NP\mathbf P\neq\mathbf{NP}. Since Boolean satisfiability (SAT) is NP\mathbf{NP}-complete [2, 3], the problem is equivalent to asking whether SAT is in P\mathbf P. To prove P≠NP\mathbf P\neq\mathbf{NP}, one must show that no polynomial-time Turing machine decides SAT.

Background

Polynomial time became the accepted formal notion of efficient computation in the 1960s. NP\mathbf{NP} captures problems whose solutions can be verified efficiently once a short certificate is supplied. Cook [2] and, independently, Levin [3] proved that SAT is NP\mathbf{NP}-complete: every language in NP\mathbf{NP} reduces to SAT by a polynomial-time many-one reduction. Karp [4] then showed that 21 classical combinatorial problems, including clique, vertex cover and Hamiltonian cycle, are NP\mathbf{NP}-complete. Thousands of problems are now known to be NP\mathbf{NP}-complete, and a polynomial-time algorithm for any one of them would give one for all.

The question matters well beyond complexity theory. A proof of P=NP\mathbf P=\mathbf{NP} with a practical algorithm would break most public-key cryptography and would make finding proofs of bounded length as easy as checking them. The separation P≠NP\mathbf P\neq\mathbf{NP} is widely believed, and it underlies modern cryptography as an assumption. [1, 9]

Equivalent formulations
  1. 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

  2. Let P\bold P denote the class of problems solvable in polynomial time, and let NP\bold N\bold P denote the class of problems whose proposed solutions can be verified in polynomial time.

    P versus NP conjecture.

    P≠NP.\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
  1. S. Cook, "The P versus NP problem", in J. Carlson, A. Jaffe and A. Wiles (eds.), The Millennium Prize Problems, Clay Math. Inst. and AMS (2006). Clay PDF
  2. S. A. Cook, "The complexity of theorem-proving procedures", Proc. 3rd Annual ACM Symposium on Theory of Computing (1971), 151–158. doi:10.1145/800157.805047
  3. L. A. Levin, "Universal sequential search problems", Problemy Peredachi Informatsii 9 (1973), no. 3, 115–116.
  4. R. M. Karp, "Reducibility among combinatorial problems", in Complexity of Computer Computations, Plenum (1972), 85–103. doi:10.1007/978-1-4684-2001-2_9
  5. T. Baker, J. Gill and R. Solovay, "Relativizations of the P=?NP\mathcal P=?\mathcal{NP} question", SIAM J. Comput. 4 (1975), 431–442. doi:10.1137/0204037
  6. A. A. Razborov and S. Rudich, "Natural proofs", J. Comput. System Sci. 55 (1997), 24–35. doi:10.1006/jcss.1997.1494
  7. S. Aaronson and A. Wigderson, "Algebrization: a new barrier in complexity theory", ACM Trans. Comput. Theory 1 (2009), no. 1, 1–54. doi:10.1145/1490270.1490272
  8. R. Williams, "Nonuniform ACC circuit lower bounds", J. ACM 61 (2014), no. 1, 1–32. doi:10.1145/2559903
  9. S. Aaronson, "P=?NPP\overset{?}{=}NP", in Open Problems in Mathematics, Springer (2016), 1–122. doi:10.1007/978-3-319-32162-2_1
  10. J. Håstad, "Almost optimal lower bounds for small depth circuits", Proc. 18th Annual ACM Symposium on Theory of Computing (1986), 6–20. doi:10.1145/12130.12132
  11. Wikipedia, P versus NP problem.

Source: Clay Mathematics Institute

Progress summary

Refreshed
Open

The problem remains open: no accepted proof shows whether efficiently checkable problems can always be solved efficiently.

Cook established the central framework in 1971, and Karp showed in 1972 that many important problems are complete for this class. A polynomial-time algorithm for Boolean satisfiability would settle the question affirmatively, while proving no such algorithm exists would settle it negatively.

Known results

  • P⊆NP\mathbf{P}\subseteq\mathbf{NP} by definition.
  • Boolean satisfiability is NP\mathbf{NP}-complete (Cook, 1971); Karp established twenty-one natural NP\mathbf{NP}-complete problems (1972).
  • Baker, Gill, and Solovay (1975) constructed oracle worlds with both P=NP\mathbf{P}=\mathbf{NP} and P≠NP\mathbf{P}\ne\mathbf{NP}.
  • Razborov–Rudich natural-proofs and Aaronson–Wigderson algebrization barriers exclude broad families of circuit and relativizing methods.

Current status (as of October 2026): P⊆NP\mathbf{P}\subseteq\mathbf{NP} and the completeness and barrier results are established, but neither P=NP\mathbf{P}=\mathbf{NP} nor P≠NP\mathbf{P}\ne\mathbf{NP} has an accepted proof.

Sources

Solutions 1

Solution to the P vs. NP problem, based on arguments that resolve previously demonstrated methods and theorems.See full solutionHide full solution

Notes: Excludes about 7 conversations with ChatGPT, so it's just Gemini.

  • MANUSCRITO CIENTÍFICO OFICIAL.pdf117,270 bytesOpen