# P versus NP problem
The P versus NP problem asks whether every decision problem whose solutions can be verified quickly can also be solved quickly: in formal terms, it asks if each language recognizable by a nondeterministic algorithm in polynomial time can likewise be recognized by a deterministic one running in polynomial time[1](https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf). It is one of the seven Clay Mathematics Institute Millennium Prize Problems, each carrying a US$1 million award from a US$7 million prize fund set up when the institute established the list[2](https://www.claymath.org/wp-content/uploads/2022/02/MPPc.pdf). The majority of complexity theorists hold that P ≠ NP; however, by 2025, nobody has found a polynomial-time algorithm for even one NP-complete problem, and equally, nobody has shown that such an algorithm is impossible.[1](https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf) • [3](https://www.arxiv.org/pdf/2508.13166)
| Key fact | Detail |
|---|---|
| The question | Is every problem with efficiently verifiable solutions (NP) also efficiently solvable (P)? Formally: is every language accepted nondeterministically in polynomial time also accepted deterministically in polynomial time?[1](https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf) • [4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/) |
| Prize status | One of seven Clay Millennium Prize Problems; US$1 million per problem from a US$7 million fund[2](https://www.claymath.org/wp-content/uploads/2022/02/MPPc.pdf) |
| Bridge theorem | Cook (1971) showed every nondeterministic polynomial-time recognition problem reduces to propositional tautology, founding NP-completeness[5](https://dl.acm.org/doi/10.1145/800157.805047) |
| Scale of the catalog | Known examples include Clique, 3-Coloring, and Traveling Salesman[6](https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/) |
| A proven upper bound for 3-SAT | Approximately 1.5n for n variables[1](https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf) |
| Practical solvers | Competition SAT solvers can often settle satisfiability of formulas with one million variables[4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/) |
| Expert belief | Most complexity theorists believe P ≠ NP[1](https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf) |
| Proven barriers | Relativization, natural proofs, and algebrization have each been shown insufficient to resolve the problem[3](https://www.arxiv.org/pdf/2508.13166) |
## Formal definitions
**P** is the class of decision problems solvable by an algorithm in a number of steps bounded by some fixed polynomial in the length of the input, formalized on the [Turing machine](https://www.edgepedia.org/turing-machine) model introduced by [Alan Turing](https://www.edgepedia.org/alan-turing) in 1936[1](https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf). Equivalently, P is the class of problems solvable by a standard digital computer in time upper-bounded by a fixed power of the input length[7](https://www.scottaaronson.com/papers/pnp.pdf). [Jack Edmonds](https://www.edgepedia.org/jack-edmonds) in 1965 suggested this formal definition of "efficient computation" when he gave an efficient algorithm for matching[4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/).
**NP** is the class of problems for which, if the answer is "yes," there is a polynomial-size proof that a Turing machine can verify in polynomial time; it can also be defined via polynomial-time checking relations[7](https://www.scottaaronson.com/papers/pnp.pdf) • [1](https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf). The asymmetry between checking and solving is concrete: verifying that 300 people form a clique requires checking 44,850 pairs, which is quick, while finding such a clique is not known to be in P[6](https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/). It is immediate that P ⊆ NP, so the question is whether the containment is proper[7](https://www.scottaaronson.com/papers/pnp.pdf).
A problem is NP-hard if an algorithm for it can be used, via a polynomial-time reduction, to solve any NP problem; a problem that is both NP and NP-hard is NP-complete[8](https://www.britannica.com/science/P-versus-NP-problem). NP-complete problems include Clique, Hamiltonian Cycle, and 3-Coloring: an efficient algorithm for any one yields efficient algorithms for all of NP[4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/). Cook's 1971 STOC paper showed that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be reduced to determining whether a given propositional formula is a tautology[5](https://dl.acm.org/doi/10.1145/800157.805047). Karp's 1971 paper then established polynomial-time reducibility among 21 combinatorial problems and introduced the standard P and NP notation[9](https://www.cs.cmu.edu/~15455/resources/Karp1971.pdf). The three conceivable resolutions are: prove P ≠ NP, prove P = NP, or prove that the statement is independent of a specified formal system[10](https://people.cs.rutgers.edu/~allender/papers/advances.in.computing.pdf).
## History
In 1965 Jack Edmonds gave an efficient matching algorithm and suggested the formal definition of efficient computation as time a fixed polynomial of the input size, from which the class P was named[4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/). Cook, Levin, and Karp then developed the initial theory of [NP-completeness](https://www.edgepedia.org/np-completeness), work that generated multiple ACM Turing Awards; in the 1970s hundreds more problems were shown NP-complete, as cataloged by Garey and Johnson[4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/). [David S. Johnson](https://www.edgepedia.org/david-s-johnson)'s history of NP-completeness, 1954–2012, records the founders' recognition with the [Fulkerson Prize](https://www.edgepedia.org/fulkerson-prize) in discrete mathematics in 1979, the ACM Turing Award in 1985, and the ORSA/TIMS von Neumann Theory Prize in 1990[11](https://www.maths.tcd.ie/EMIS/journals/DMJDMV/vol-ismp/50_johnson-david.pdf). The Clay Mathematics Institute incorporated on September 25, 1998, and established the seven Millennium Prize Problems including P versus NP[2](https://www.claymath.org/wp-content/uploads/2022/02/MPPc.pdf). The problem turned 50 in 2021 with its resolution far out of reach[6](https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/).
## Why it is hard: known barriers
To prove P ≠ NP it would suffice to show that an NP-complete problem cannot be solved by polynomial-size circuits of AND, OR, and NOT gates[4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/). This circuit-complexity approach has produced restricted successes: in 2010 Ryan Williams showed that NEXP does not have small constant-depth circuits with Mod 6 gates[6](https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/). But several broad proof approaches have been shown insufficient. Relativizing proofs, which remain valid when computation is given access to an oracle, cannot by themselves resolve the relationship between P and NP, as shown by Baker, Gill, and Solovay[3](https://www.arxiv.org/pdf/2508.13166). Natural proofs, based on circuit lower bounds, are ineffective for a direct resolution under the assumption that one-way functions exist, per Razborov and Rudich[3](https://www.arxiv.org/pdf/2508.13166) • [4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/). Aaronson and Wigderson's algebrization barrier shows the problem cannot be resolved by any algebrizing proof technique either[10](https://people.cs.rutgers.edu/~allender/papers/advances.in.computing.pdf). No significantly new circuit lower bounds appeared in the 20 years before the 2009 survey[4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/). Against pessimism, [Scott Aaronson](https://www.edgepedia.org/scott-aaronson) has argued that in light of circuit lower bounds by Furst–Saxe–Sipser, Ajtai, Razborov, and Smolensky, P vs. NP is no more likely to be formally independent of strong logical theories than Goldbach's Conjecture or the Riemann Hypothesis[12](https://scottaaronson.com/papers/indep.pdf).
## By the numbers
A proven upper bound on an algorithm for solving 3-SAT is approximately 1.5n, where n is the number of variables in the input formula[1](https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf). Against that worst-case exponential, competition SAT solvers can often settle satisfiability of formulas of one million variables[4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/), and with refined heuristics, fast processors, specialized hardware, and distributed cloud computing, practitioners can often solve satisfiability and mixed-integer programming instances with tens of thousands of variables and hundreds of thousands or even millions of constraints[6](https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/). A 2024 Nature-family article tabulates the best classical algorithms for each of [Karp's 21 NP-complete problems](https://www.edgepedia.org/karps-21-np-complete-problems), listing solvers such as Chaff, GRASP, GSAT, and WalkSAT for SAT and the Concorde solver for TSP[13](https://www.nature.com/articles/s44335-024-00015-z/tables/4). There are many known NP-complete problems[6](https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/).
## How it compares with undecidability and related questions
P versus NP is a question of efficiency, not computability. Complexity theory defines feasible decidability as solvability in polynomial time, and P can be formally shown distinct from EXP, exponential time; so some problems are provably infeasible without being undecidable[14](https://plato.stanford.edu/entries/computational-complexity/). This separates the question from undecidability, which concerns whether any algorithm exists at all[14](https://plato.stanford.edu/entries/computational-complexity/). The known containment chain is L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP ⊆ NEXP ⊆ EXPSPACE, situating P vs NP among sibling class-separation questions like P vs PSPACE[14](https://plato.stanford.edu/entries/computational-complexity/).
## Practical significance
**Cryptography.** If P = NP then public-key cryptography is impossible; an efficient algorithm for NP would break all cryptosystems except information-theoretically secure ones such as one-time pads and some quantum-physics-based schemes[4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/) • [6](https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/). Modern cryptography relies on the assumption that factoring the product of two large primes is not in P: verifying the product is easy in polynomial time, but computing the two prime factors is hard[8](https://www.britannica.com/science/P-versus-NP-problem). Assuming P ≠ NP is not enough for public-key protocols; strong average-case assumptions about the difficulty of factoring or related problems are needed[4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/). Proving that an NP problem used in cryptography is super-polynomially hard would itself imply P ≠ NP, so cryptography must rely on hardness assumptions that cannot currently be proven[15](https://pqcc.org/an-inconvenient-truth-about-modern-cryptography/). A further wrinkle: although solving an NP-complete problem would allow breaking encryption, the reverse is not true, because the intractable problems underlying most encryption schemes are not themselves NP-complete[16](https://www.scientificamerican.com/article/the-math-mystery-that-connects-sudoku-flight-schedules-and-protein-folding/).
**Optimization and verification.** Dramatic advances in algorithms and hardware have allowed tackling many NP-complete problems while making little progress breaking cryptographic systems[6](https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/). NP-problem-solving tools have been used successfully in circuit and code verification, computational biology, system security, product and packaging design, financial trading, and solving difficult mathematical problems[6](https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/).
**Why fast solvers coexist with P ≠ NP.** Worst-case NP-completeness does not fix typical-case difficulty. It would be wrong to say NP is easy "in practice," and equally wrong to take [NP-hardness](https://www.edgepedia.org/np-hardness) as the final word on a problem's complexity when instances have known generation structure; understanding typical-case complexity and the power and limits of heuristics matters[17](https://introtcs.org/public/lec_14_PvsNP.html). Real-world cryptographic attacks stem from bad implementations, weak random number generators, or human error rather than breaking the cryptography itself[6](https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/).
**If P = NP.** A proof would yield short logical proofs of theorems that have reasonable-length proofs, and if the algorithm were efficient in practice, one could search for formal proofs of the other [Millennium](https://www.edgepedia.org/millennium) conjectures, effectively resolving not merely one Millennium Problem but all seven[4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/) • [7](https://www.scottaaronson.com/papers/pnp.pdf).
## Quantum computing and the practical landscape
Lov Grover found a quantum algorithm that works on general NP problems but achieves only a quadratic speed-up, with evidence that those techniques will not go further[4](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/). Separately, since Shor's 1994 paper, factoring and discrete logarithm problems, including elliptic curves, could in theory be solved efficiently on a powerful quantum computer; in 2016 NIST launched its Post-Quantum Cryptography project to select quantum-resistant algorithms[15](https://pqcc.org/an-inconvenient-truth-about-modern-cryptography/).
## Recent developments
No accepted resolution exists as of 2025[3](https://www.arxiv.org/pdf/2508.13166). In 2024–2025 a paper by Deng claimed a polynomial-time algorithm deciding 3-coloring for graphs of maximum degree 4, which would imply P = NP; a 2025 arXiv refutation identified a critical error, that the proof conflates subgraphs with induced subgraphs, invalidating it[18](https://arxiv.org/pdf/2507.09018). The claim targeted a genuinely hard case: Holyer showed in 1981 that determining whether a graph is 3-colorable is NP-complete even when every vertex has degree at most 4[18](https://arxiv.org/pdf/2507.09018). Alongside refereed work, unvetted claims continue to appear: a 2025 self-published Zenodo record claimed a constructive proof of P ≠ NP via Kolmogorov-complexity witness incompressibility, asserting resistance to relativization, natural proofs, and algebrization; Zenodo deposits carry no peer review[19](https://zenodo.org/records/15529778). As a 2025 survey notes, after many years of study nobody has found a polynomial-time method for solving any NP-complete problem, but neither has anyone shown that such a method is impossible[3](https://www.arxiv.org/pdf/2508.13166). Mainstream research continues indirectly through proof complexity, where Cook and Reckhow's result that NP ≠ coNP holds if and only if every propositional proof system has super-polynomial lower bounds, including Extended Frege, frames the accepted route toward separation[20](https://dl.acm.org/doi/pdf/10.1145/3801091).
## References
1. [Stephen Cook. The P versus NP Problem (official Clay Millennium problem statement), Clay Mathematics Institute.](https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf)
2. [The Millennium Prize Problems, Clay Mathematics Institute.](https://www.claymath.org/wp-content/uploads/2022/02/MPPc.pdf)
3. [Survey of proof techniques and barriers for the P versus NP question, arXiv (2025).](https://www.arxiv.org/pdf/2508.13166)
4. [The Status of the P versus NP Problem, Communications of the ACM (2009).](https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/)
5. [Stephen A. Cook (1971). The complexity of theorem-proving procedures, STOC.](https://dl.acm.org/doi/10.1145/800157.805047)
6. [Fifty Years of P vs. NP and the Possibility of the Impossible, Communications of the ACM (2021).](https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/)
7. [Scott Aaronson. P ≟ NP (survey).](https://www.scottaaronson.com/papers/pnp.pdf)
8. [P versus NP problem, Encyclopaedia Britannica.](https://www.britannica.com/science/P-versus-NP-problem)
9. [Richard M. Karp (1971). Reducibility Among Combinatorial Problems.](https://www.cs.cmu.edu/~15455/resources/Karp1971.pdf)
10. [Eric Allender. A Status Report on the P versus NP Question.](https://people.cs.rutgers.edu/~allender/papers/advances.in.computing.pdf)
11. [David S. Johnson. A Brief History of NP-Completeness, 1954–2012.](https://www.maths.tcd.ie/EMIS/journals/DMJDMV/vol-ismp/50_johnson-david.pdf)
12. [Scott Aaronson. Is P vs. NP Formally Independent?](https://scottaaronson.com/papers/indep.pdf)
13. [Table 4: Best classical algorithms for Karp's 21 NP-complete problems, Nature npj Unconventional Computing (2024).](https://www.nature.com/articles/s44335-024-00015-z/tables/4)
14. [Computational Complexity Theory, Stanford Encyclopedia of Philosophy.](https://plato.stanford.edu/entries/computational-complexity/)
15. [An inconvenient truth about modern cryptography, Post-Quantum Cryptography Coalition.](https://pqcc.org/an-inconvenient-truth-about-modern-cryptography/)
16. [The math mystery that connects Sudoku, flight schedules and protein folding, Scientific American.](https://www.scientificamerican.com/article/the-math-mystery-that-connects-sudoku-flight-schedules-and-protein-folding/)
17. [Introduction to Theoretical Computer Science: What if P equals NP?](https://introtcs.org/public/lec_14_PvsNP.html)
18. [Critical examination of Deng's "P=NP" claim, arXiv (2025).](https://arxiv.org/pdf/2507.09018)
19. [A Minimal Constructive Proof That P ≠ NP via Witness Incompressibility, Zenodo (2025).](https://zenodo.org/records/15529778)
20. [Towards P≠NP from Extended Frege Lower Bounds, ACM (2025).](https://dl.acm.org/doi/pdf/10.1145/3801091)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Computability theory › Undecidability results and applications*
*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license