Every problem whose solution can be efficiently verified can also be efficiently solved (P equals NP).
Assessment
No credible evidence found, though the claim is not contradicted.
Whether P equals NP is the central open problem of theoretical computer science and one of the seven Clay Millennium Prize problems. It asks whether every decision problem whose yes-instances have short, polynomial-time-checkable certificates can itself be decided in polynomial time. Neither answer has been proved: no claimed proof in either direction has withstood expert scrutiny, and no superpolynomial lower bound is known for any NP problem in a general model of computation, so equality remains a logical possibility that nothing on the record excludes.
The weight of informed opinion and of the available heuristic evidence, however, runs firmly against equality. Because Boolean satisfiability is NP-complete, a single polynomial-time algorithm for any one of the thousands of known NP-complete problems would settle the matter, yet none has been found in more than fifty years, and the boundary between problems known to be in P and problems known to be NP-complete has never once been crossed. Equality would also collapse the polynomial hierarchy and would rule out the one-way functions on which modern cryptography is believed to rest. Polls of the field find that most theorists expect P to differ from NP: 88 percent of respondents in William Gasarch's 2019 poll, up from 61 percent in 2002. Scott Aaronson's 2017 survey describes the field's confidence in inequality as comparable to its confidence in the Riemann hypothesis.
A credible minority dissents. Donald Knuth has said he has come to believe that P equals NP, on the grounds that it is hard to believe so many able people would fail to prove inequality if it were true, and that among the vast number of algorithms running in time n to some enormous power it is hard to believe all fail; he expects any proof of equality to be non-constructive and of no practical use. Richard Lipton professes agnosticism. These are considerations of plausibility rather than partial results, and the difficulty of proving lower bounds is itself well understood: relativizing, natural, and algebrizing techniques provably cannot resolve the question, which explains the absence of a proof of inequality without lending support to equality.
The claim therefore stands as an open conjecture that the field regards as very probably false. It would be settled by a polynomial-time algorithm for any NP-complete problem, or by a superpolynomial lower bound for satisfiability; neither is in sight.
Full reasoning: the evidence and decisions behind this verdict
The claim is a mathematical proposition that is neither proved nor refuted, so the verdict rests on the heuristic evidence and the distribution of credible expert judgment. Stephen Cook's official problem description for the Clay Mathematics Institute (www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf) fixes the definitions and states the question as open; it also remarks that NP-completeness explains why seeking a polynomial-time algorithm for an NP-complete problem is probably a waste of time. Lance Fortnow's April 2025 blog post confirms the problem remained open as of that date and sorts the stream of amateur claimed proofs into recurring failure types (blog.computationalcomplexity.org/2025/04/p-v-np-papers-galore.html); a web search for recent developments turned up only unrefereed preprints on SSRN, TechRxiv, ResearchGate and Medium claiming resolutions in both directions, none of which has been accepted by the community.
Evidence against the claim. Aaronson's survey (www.scottaaronson.com/papers/pnp.pdf, section 3) gives the strongest consolidated case: the "invisible fence" between the thousands of problems shown NP-complete and the thousands shown to be in P, which has never been breached even where sharp thresholds exist (Håstad's 7/8 threshold for Max-3-SAT, Valiant's mod-7 accidental algorithm); the hierarchy theorems, which prove P differs from EXP and so make most pairs of classes unequal; the failure of a global software industry to find fast inversion of arbitrary one-way functions; and the observation that the difficulty of lower bounds explains the missing proof without supporting equality. These map onto the subclaims no polynomial-time algorithm is known for any NP-complete problem, if P equals NP the polynomial hierarchy collapses to P (a theorem, so its weight comes from the implausibility of the consequent), and cryptographic one-way functions exist. Expert opinion: Gasarch's third poll (www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf) records 109 of 124 respondents (88%) for inequality and 15 (12%) for equality in 2019, against 61%/9% in 2002 and 83%/9% in 2012; among those who believe inequality, 92.5% also believe the polynomial hierarchy does not collapse. The poll also records that in a hypothetical where trusted colleagues announce a resolution without saying which way, 80% would still guess inequality; Gasarch himself says he would switch to equality, reflecting the widely shared view that a proof of equality could arrive suddenly while a proof of inequality is far off.
Evidence for the claim. Knuth's 2014 interview (www.informit.com/articles/article.aspx?p=2213858) is the most prominent affirmation. His reasons are that it is hard to believe inequality holds while so many brilliant people have failed to prove it, and that among all algorithms running in n to a huge power M it is hard to believe every one fails; the Robertson-Seymour theorem, which guarantees polynomial-time algorithms nobody can write down, tipped him. He calls part of this reasoning naive and expects any proof of equality to be non-constructive. Poll respondents such as András Salamon and Dmytro Taranovsky express substantial uncertainty on the majority side. None of this is a partial result: no subexponential algorithm for an NP-complete problem, no collapse of any level of the hierarchy, and no structural theorem that would follow more naturally from equality is on record. The argument no superpolynomial lower bound has been proven for any NP problem in a general model of computation establishes only that equality is not excluded.
Weighing. The instance set is lopsided (three denials or arguments for inequality from Aaronson and Fortnow, one affirmation from Knuth, three neutral statements of the problem from Clay, Cook and Fortnow), and the two Aaronson sources are one voice. The lopsidedness matches the poll data rather than an artefact of collection. "Contested" was considered, since a credible mathematician affirms the claim; it was rejected because the affirmation rests on plausibility considerations that its author discounts and that the majority has answered (the difficulty of lower bounds is explained by the barrier results), and because §18 asks for the state of the argument rather than the existence of dissent. "Contradicted" was rejected because nothing has been proved. "Unsupported" fits an open conjecture with no evidence in its favour beyond plausibility, which the mathematics skill notes is the ordinary status of most open problems. The credence of about 0.07 sits slightly below the poll's 12% share for equality, on the view that some poll affirmations are contrarian, and above the near-zero many theorists would give, because no proof exists and the history of surprising polynomial-time algorithms (primality, linear programming, matching) counsels humility. The minor encoding mismatch on the Aaronson lecture instance (the stored page carries an HTML entity where the quotation has the inequality sign) does not affect its content.
What would change the verdict: a refereed and independently expounded proof either way; a machine-checked proof of a faithful formal statement; a polynomial-time algorithm for any NP-complete problem, however impractical; or a subexponential algorithm or hierarchy collapse that materially shifted expert credence.
Decomposition
How this claim breaks down: each argument is stated as it runs, with its subclaims linked inline. ↗︎ opens a subclaim; the map shows how they fit together.
Given that Boolean satisfiability is NP-complete, so that one polynomial-time algorithm for any NP-complete problem would settle the question, the fact that no polynomial-time algorithm is known for any NP-complete problem after decades of effort on thousands of them is inductive evidence that none exists. Because if P equals NP the polynomial hierarchy collapses to P, and because equality would rule out the widely believed proposition that cryptographic one-way functions exist, equality would carry consequences the field regards as implausible; that most theoretical computer scientists believe that P is not equal to NP reflects the weight given to these considerations. Together they make P equals NP unlikely without proving it false.
The inference is inductive, not deductive: granting every premise, it makes equality improbable rather than false, and the argument is honest about that. Its weight rests chiefly on the absence of any polynomial-time algorithm for an NP-complete problem across thousands of problems and fifty years, a settled fact, and on the belief that one-way functions exist, which is itself an unproven conjecture and so cannot carry more confidence than it has. The hierarchy collapse is a theorem whose evidential force depends entirely on how implausible one finds the collapse, and the poll result records the field's judgment rather than adding independent evidence. The caveat is Knuth's: the failure to find an algorithm is also what one would expect if a polynomial-time algorithm exists but has an astronomically large exponent or can only be shown to exist non-constructively.
Because no superpolynomial lower bound has been proven for any NP problem in a general model of computation, nothing in the proven record excludes a polynomial-time algorithm for satisfiability, possibly one with an astronomically large exponent or established non-constructively, so P equals NP remains a live logical possibility that the inductive evidence against it cannot close.
The inference goes through, but it establishes only that equality is not excluded, not that it is likely: from the absence of any superpolynomial lower bound for an NP problem in a general model, which is an uncontested description of the state of the art, it follows that a polynomial-time algorithm for satisfiability remains logically possible. The premise is settled, so the argument is secure as far as it reaches; its limit is that the absence of a lower bound is well explained by the known barriers to proving lower bounds and is therefore weak evidence for equality itself.
Because relativizing, natural, and algebrizing proof techniques cannot resolve whether P equals NP, any resolution must use methods outside the families that have driven most of complexity theory, and given that no claimed proof that P equals NP or that P differs from NP has withstood expert scrutiny, the question has no answer on the record in either direction; the claim's status therefore rests on heuristic evidence rather than proof.
The inference holds: given that relativizing, natural, and algebrizing techniques cannot resolve the question, which is a set of proved theorems (Baker, Gill and Solovay; Razborov and Rudich; Aaronson and Wigderson), and that no claimed proof in either direction has survived scrutiny, the question is open and any assessment must rest on heuristic evidence. Both premises are settled in the discourse. The argument is neutral on the answer; it fixes the kind of evidence that can bear on the claim and explains why the missing proof of inequality is not itself evidence for equality.
Provenance
Where this claim has been said, linked to its canonical form.
one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure.
If it is easy to check that a solution to a problem is correct, is it also easy to solve the problem? This is the essence of the P vs NP question.
Asserted without evidence of the source's own. The Clay Mathematics Institute page presents the question as unsolved and takes no side, though it remarks that NP problems certainly seem hard. It offers no argument for either answer and is a statement of the problem, not a voice on it.
NO. People that think P=NP are like people who think Elvis is still alive.
Quoted respondent in William Gasarch's 2019 poll of theorists, in which 109 of 124 respondents (88%) answered that P is not equal to NP and 15 (12%) that P equals NP.
Asserted without evidence of the source's own. The quoted line is a bare expression of conviction, offered without argument; it is representative of the poll's large majority. The article itself takes no side and records opinion, and its author notes elsewhere in the piece that he would switch to believing P equals NP if told the question had been resolved without being told how. Worth reading closely: The poll is the best available measurement of expert opinion on the question across three decades (2002, 2012, 2019), and it also records the minority of serious researchers who lean toward equality.
As you say, I've come to believe that P = N P , namely that there does exist an integer M and an algorithm that will solve every n -bit problem belonging to the class N P in n M elementary steps.
Answering Andrew Binstock's question about his stated conviction at the 2012 ACM Turing Centennial. Knuth gives two reasons: the difficulty of believing so many brilliant people have failed to find a proof of inequality, and the vast number of candidate algorithms with an enormous exponent M; he expects any proof of equality to be non-constructive and practically useless, citing the Robertson–Seymour graph minor theorem as a model.
Asserted without evidence of the source's own. Knuth presents his position as a personal conviction resting on two heuristics he himself calls naive: that so many able people have failed to prove inequality, and that among the enormous number of algorithms running in n to a huge power it is hard to believe all fail. The Robertson-Seymour graph minor theorem, which guarantees polynomial-time algorithms nobody can write down, is what he says tipped him. It is the best-known dissent from the field's majority view and is offered as intuition rather than evidence. Worth reading closely: It is the most prominent statement of the minority position and gives its actual reasons, which a fair account of the disagreement should present in their strongest form.
Well, we certainly believe P≠NP. Indeed, we don't even believe there's a general way to solve NP problems that's dramatically better than brute-force search through every possibility.
Lecture notes introducing P and NP, stating the field's working belief before explaining why the separation is hard to prove.
The source's own evidence bears what it asserts. The lecture states the belief as the field's consensus and gives the informal grounds for it (the apparent unavoidability of brute-force search, the theory of NP-completeness), while candidly noting that the same intuition has been wrong about primality, matching, and edit distance. It is a considered expert statement, not a proof, and presents itself as such. The quoted passage was not found in the stored copy of this source.
Problem Statement. Does P = NP?
The official Clay Mathematics Institute problem description defines P and NP formally via Turing machines and polynomial-time checking relations, then states the problem as an open question; it notes that NP-completeness "explains why it is probably a waste of time looking for a polynomial-time algorithm for an NP-complete problem."
Asserted without evidence of the source's own. Cook's description is the canonical formal statement of the problem. It takes no side in the problem statement itself, though its discussion of NP-completeness remarks that seeking a polynomial-time algorithm for an NP-complete problem is probably a waste of time. It is the document a reader should consult for the exact definitions of the classes. Worth reading closely: It fixes the precise definitions of P and NP that any formal statement of the claim must match, and it records the founder's own view of why the problem is hard.
P v NP is still the most important problem in theoretical computer science and perhaps all of mathematics, and not that difficult to understand, at least on an intuitive level.
A complexity theorist describing the stream of amateur claimed proofs he receives, sorting them into three recurring failure categories, and stating that the question remains open as of 2025.
Asserted without evidence of the source's own. The post states the question as open in 2025 and offers no argument for either answer; its value is as a contemporary confirmation that no claimed proof has been accepted and as a catalogue of how claimed proofs typically fail.
In this section, I'd like to explain why, despite our limited understanding, many of us feel roughly as confident about P̸ = NP as we do about (say) the Riemann Hypothesis, or other conjectures in math—not to mention empirical sciences—that most experts believe without proof.
A 120-page survey of the P versus NP problem. Section 3, "Beliefs About P=?NP", argues that P differs from NP, citing the "invisible fence" between thousands of NP-complete problems and thousands of problems in P, the hierarchy theorems, and the failure of the software industry to find fast inversion of one-way functions; it also records Knuth's dissent and Lipton's agnosticism and the 2002 and 2012 Gasarch polls.
The source's own evidence bears what it asserts. The survey argues for inequality as a well-founded conjecture rather than a theorem, and it is unusually careful to give the actual grounds: that thousands of NP-complete problems and thousands of problems in P have never been found to coincide, that hierarchy theorems make most pairs of classes unequal, and that the difficulty of lower bounds explains why no proof exists even if the conjecture is true. It records the dissenting views of Knuth and Lipton and the poll numbers, and regards independence from set theory as unlikely. It is the fullest single statement of the mainstream position. Worth reading closely: It gathers every major line of heuristic evidence and every known barrier in one place, with references, and any reassessment should start from it.
How these sources relate
- PHYS771 Lecture 6: P, NP, and Friends and https://www.scottaaronson.com/papers/pnp.pdf share an author. Both are by Scott Aaronson: the 2017 survey "P =? NP" carries his byline, and the PHYS771 lecture notes are hosted on his site under his name. They are one voice on the claim.
Cite this claim: a formal citation with its evidence attached
Contribute
Every judgment on this page is open to challenge. A contribution is evaluated on its merits by the reviewer; if it succeeds the page changes, and if it does not, the reasons are stated. Either way the exchange becomes part of the claim’s public record.
The attention this claim received was paid for by a funded mandate. Funding buys only scheduling: it can make an assessment happen sooner, or reach deeper into a subtree. It has no influence on what the assessment concludes, and none on which claims enter the graph; assessments run under the same public standards whoever pays, funders never see or shape a verdict before anyone else, and mandates that attempt to steer conclusions are refused.
Created by extractor · Sep 13, 2026. Every judgment on this page is accompanied by a reasoning trace.