P versus NP
Can every problem whose answer is quick to check also be solved quickly?
Summary
Why it is open
"Polynomial time" means that the number of steps is bounded by a fixed polynomial in the length of the input. A problem is in NP when a proposed solution, called a certificate, can be checked in polynomial time [5]. Every problem in P is also in NP, since a checker can ignore the certificate and solve the problem directly [8]. The open question is whether the reverse holds.
A resolution is a proof either way. To show P = NP it would be enough to give a polynomial-time algorithm for any one NP-complete problem, such as 3-SAT; to show P ≠ NP it would be enough to prove that some NP-complete problem needs Boolean circuits of super-polynomial size [5]. Such a proof need not be practical: a proof of P = NP might be non-constructive and yield no usable algorithm [5]. For the Clay Mathematics Institute's prize, a solution must appear in a qualifying outlet, at least two years must pass after publication, and it must gain general acceptance in the mathematics community [15].
A proof of P ≠ NP must rule out every possible algorithm, including ones nobody has imagined, and current techniques are nowhere near that. In Stephen Cook's description of the problem, it is consistent with present knowledge that satisfiability could be solved in linear time on a multitape Turing machine [5]. For Boolean circuits, it is not known whether any explicit function in NP needs circuits of size 10n, where n is the number of input bits [12]. Three "barrier" theorems show that whole families of proof techniques cannot settle the question (see below) [3, 4, 8]. Scott Aaronson regards the speculation that P ≠ NP is unprovable from the standard axioms of mathematics as unlikely [8].
What is known
Origins. Stephen Cook introduced NP-completeness in 1971 and proved that satisfiability (SAT) and 3-SAT are NP-complete [1, 5]. Leonid Levin independently defined "universal search problems", with six examples including satisfiability, published in 1973 [2, 5]. In 1972 Richard Karp showed that many other natural combinatorial problems are NP-complete and introduced the notation P and NP [5]. Earlier forms of the question appear in a 1955 letter from John Nash to the US National Security Agency and a 1956 letter from Kurt Gödel to John von Neumann [8].
What NP-completeness means. A polynomial-time algorithm for any NP-complete problem would give one for every problem in NP [5]. Hundreds of NP-complete problems are known, among them graph problems such as three-colouring that underlie many scheduling and routing tasks [5]. Some problems in NP, such as graph isomorphism and a decision version of integer factoring, are not known to be either in P or NP-complete [5]. If P = NP, the complexity assumptions behind most current cryptography would be false, and a practical algorithm would let a computer find a formal proof of any theorem that has a proof of reasonable length [5].
What researchers believe. Most complexity theorists believe that P ≠ NP [5]. In William Gasarch's third poll, run in 2018 and published in 2019, 109 of 124 respondents (88%) answered P ≠ NP and 15 (12%) answered P = NP [9]. A poll records opinion, not evidence.
Proven lower bounds. Exponential lower bounds are known for restricted circuit models: monotone circuits (without NOT gates) and circuits of constant depth [5]. For proofs, Armin Haken showed in 1985 that some unsatisfiable formulas, such as those encoding the pigeonhole principle, need exponentially long refutations in the resolution proof system [8]. In 2011 Ryan Williams proved that nondeterministic exponential time (NEXP) is not contained in ACC0, polynomial-size, constant-depth circuits that may also count modulo a fixed number [7, 8]. For unrestricted circuits, the best lower bound for an explicit function reported by 2022 is only linear: 3.1n − o(n), by Jiatu Li and Tianqi Yang [12].
Barriers. In 1975 Theodore Baker, John Gill and Robert Solovay built an oracle relative to which P = NP and another relative to which P ≠ NP, so a proof technique that works unchanged in the presence of any oracle (one that "relativizes") cannot settle the question [3, 8]. In 1997 Alexander Razborov and Steven Rudich showed that "natural proofs", a class that covers the circuit lower-bound arguments known at the time, cannot prove strong lower bounds for general circuits if strong pseudorandom generators exist [4, 5]. In 2008 Aaronson and Avi Wigderson described a third barrier, algebrization: the arithmetic techniques behind results such as IP = PSPACE evade relativization but still cannot prove P ≠ NP [8].
Recent claims. Many claimed proofs have been presented over the years [5]; none has been accepted [15]. One recent claim reached a journal. Ke Xu and Guangyan Zhou's "SAT requires exhaustive search", first posted in 2023, was published online in Frontiers of Computer Science on 4 July 2025 [14]. It claims that specially constructed hard instances of constraint satisfaction and SAT cannot be solved without exhaustive search, "which is stronger than P ≠ NP" [14]. In a comment published in the same journal in September 2025, Eric Allender and Ryan Williams argued that the argument "falls far short of a proof": it assumes, without justification, that every SAT algorithm works by reducing an instance of size n to instances of size n − 1, and for constraints with two variables the claimed lower bound is beaten by a known algorithm [13]. On 6 October 2026 the Clay Mathematics Institute still listed the problem as unsolved [15].
Main approaches
Circuit lower bounds. Every problem in P has polynomial-size circuits, so proving that an NP-complete problem needs larger circuits would prove P ≠ NP [5]. Strongest evidence: exponential bounds for monotone and constant-depth circuits [5]. Main difficulty: bounds for general circuits are still linear [12], and the natural-proofs barrier explains why familiar techniques stall [4].
Algorithms that imply lower bounds. In Williams's method, a satisfiability algorithm for a circuit class that is even slightly faster than brute force proves that NEXP lies outside that class [7, 8]. Strongest evidence: the ACC0 result, which evades all three barriers [8]. Main difficulty: the separations are far weaker than P ≠ NP: they place a class much larger than NP outside a class much smaller than general polynomial-size circuits, and when Aaronson wrote his survey, even NEXP ⊄ TC0 (constant-depth threshold circuits) was open [8].
Geometric complexity theory. In a programme pursued since the late 1990s, whose first part Ketan Mulmuley and Milind Sohoni published in 2001, they use algebraic geometry and representation theory to look for "obstructions" showing that the permanent cannot be expressed through a small determinant, an algebraic analogue of the question [6, 8]. Strongest evidence: some hypotheses can now be tested; Christian Ikenmeyer, Mulmuley and Walter showed that super-polynomially many Kronecker coefficients vanish, which Aaronson says keeps hope for obstructions alive, at least for other problems [8]. Main difficulty: Peter Bürgisser, Ikenmeyer and Greta Panova proved that the simplest kind of obstruction, occurrence obstructions, cannot separate the permanent from the determinant in the required range [10, 8].
Proof complexity. NP ≠ coNP is equivalent to saying that no propositional proof system has short proofs of every tautology [5], and NP ≠ coNP would imply P ≠ NP [8]. Strongest evidence: exponential lower bounds for resolution and for systems that generalise it [8]. Main difficulty: lower bounds for arbitrary proof systems would prove NP ≠ coNP, which is stronger than P ≠ NP, and Aaronson notes that such bounds tend to be harder than the analogous circuit lower bounds [8].
Meta-complexity. This line studies problems about complexity itself, such as how compressible a string is. Yanyi Liu and Rafael Pass proved in 2020 that one-way functions exist if and only if a time-bounded version of Kolmogorov complexity is mildly hard on average [11]. Strongest evidence: it ties the foundations of cryptography to a natural computational problem [11]. Main difficulty: an equivalence relocates the question; it does not prove either side [11].
Open sub-questions
- Beyond 3.1n. Can some function in NP be proven to need Boolean circuits of size 3.5n, or even 10n [12]?
- Threshold circuits. Is there a deterministic, better-than-brute-force algorithm that estimates how likely a constant-depth threshold circuit is to accept a random input? Via Williams's method it would give lower bounds against TC0, a target Aaronson lists as on the horizon [8].
- Tensor rank. Can an explicit d-dimensional tensor be shown to have rank above n^⌊d/2⌋? Aaronson lists this among the next targets, since such tensors are known to imply new circuit lower bounds [8].
- Multiplicity obstructions. With occurrence obstructions ruled out [10], can multiplicity obstructions separate the permanent from the determinant [8]?
- Average-case hardness. Is time-bounded Kolmogorov complexity mildly hard on average? By Liu and Pass, this is the same as asking whether one-way functions exist [11] (see the Papex page Existence of one-way functions).
- Checking a new technique. For a proposed proof strategy, does it relativize, algebrize or count as a natural proof? A strategy that does is known to be unable to separate P from NP (for natural proofs, if strong pseudorandom generators exist) [3, 4, 8].
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It does not check a proof, and it is not a submission for the Clay Mathematics Institute prize.
Key references
- Cook, S. A. (1971). The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC '71), 151–158. 10.1145/800157.805047 · Checked 06 Oct 2026
- Levin, L. A. (1973). Universal sequential search problems [Универсальные задачи перебора]. Problemy Peredachi Informatsii 9(3), 115–116; English translation in Problems of Information Transmission 9(3), 265–266. Source · Checked 06 Oct 2026
- Baker, T., Gill, J. & Solovay, R. (1975). Relativizations of the P =? NP question. SIAM Journal on Computing 4(4), 431–442. 10.1137/0204037 · Checked 06 Oct 2026
- Razborov, A. A. & Rudich, S. (1997). Natural proofs. Journal of Computer and System Sciences 55(1), 24–35. 10.1006/jcss.1997.1494 · Checked 06 Oct 2026
- Cook, S. The P versus NP problem. Official problem description, Clay Mathematics Institute (prepared for the Millennium Prize; the hosted version cites work published up to 2004). Source · Checked 06 Oct 2026
- Mulmuley, K. D. & Sohoni, M. (2001). Geometric complexity theory I: an approach to the P vs. NP and related problems. SIAM Journal on Computing 31(2), 496–526. 10.1137/S009753970038715X · Checked 06 Oct 2026
- Williams, R. (2014). Nonuniform ACC circuit lower bounds. Journal of the ACM 61(1), 2:1–2:32. 10.1145/2559903 · Checked 06 Oct 2026
- Aaronson, S. (2016). P =? NP. In Open Problems in Mathematics, Springer, 1–122. 10.1007/978-3-319-32162-2_1 · Checked 06 Oct 2026
- Gasarch, W. I. (2019). Guest column: the third P =? NP poll. ACM SIGACT News 50(1), 38–59. 10.1145/3319627.3319636 · Checked 06 Oct 2026
- Bürgisser, P., Ikenmeyer, C. & Panova, G. (2019). No occurrence obstructions in geometric complexity theory. Journal of the American Mathematical Society 32(1), 163–193 (published online 2018). 10.1090/jams/908 · Checked 06 Oct 2026
- Liu, Y. & Pass, R. (2020). On one-way functions and Kolmogorov complexity. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 1243–1254. 10.1109/FOCS46700.2020.00118 · Checked 06 Oct 2026
- Li, J. & Yang, T. (2022). 3.1n − o(n) circuit lower bounds for explicit functions. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC '22), 1180–1193. 10.1145/3519935.3519976 · Checked 06 Oct 2026
- Allender, E. & Williams, R. (2025). Comment on "SAT requires exhaustive search". Frontiers of Computer Science 20(1), 2001405 (published online 17 September 2025). 10.1007/s11704-025-53000-5 · Checked 06 Oct 2026
- Xu, K. & Zhou, G. (2025). SAT requires exhaustive search. Frontiers of Computer Science 19(12), 1912405 (published online 4 July 2025). 10.1007/s11704-025-50231-4 · Checked 06 Oct 2026
- Clay Mathematics Institute. P vs NP (problem page, status "Unsolved") and Millennium Prize rules. Source · Checked 06 Oct 2026
Source
Open, as listed by Clay Mathematics Institute · Millennium Prize Problems. Checked 29 Sep 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Prize
Clay Mathematics Institute · $1,000,000
Only Clay Mathematics Institute awards this prize, under its own rules. Your Papex record is separate: a signed, dated record of your work, not a prize entry.
Records on this problem
No public record addresses this problem yet.