Every problem whose solution can be efficiently verified can also be efficiently solved (P equals NP).
4 events · 1 assessment · 2 decisions
Structured and assessed
First full pass. The claim arrived with a decomposition already in place (seven subclaims grouped under three named arguments with written forms) but no assessment and no argument evaluations. Reviewed the structure and judged it sound; added one subclaim, "Cryptographic one-way functions exist" (Matcher: novel; created with importance 0.35, seed credence 0.85), to the "Heuristic case for P ≠ NP" argument, since the existence of one-way functions implies inequality and is a central plank of the mainstream case, and rewrote that argument's written form to include it. Searched the graph for a duplicate node stating inequality and found none. Canonical form kept: it is a neutral, fifteen-word statement of the proposition with the standard name in parentheses, acceptable to both sides. Importance set to 0.8 (mathematics skill anchor for P versus NP) with contestation 0.7. Provenance: read all five pre-existing sources (Gasarch 2019 poll, Aaronson lecture, Knuth interview, Cook problem description; Clay page already read) and recorded readings; added two instances found during search (Aaronson's 2017 survey, denies; Fortnow's 2025 blog post, poses) with readings; recorded shared authorship between the two Aaronson sources; wrote an immaterial source map. Raised an annoyance-level tool issue: the quote check reports not_found on the Aaronson lecture instance because the stored text retains an HTML entity for the inequality sign. Assessment: unsupported, confidence 0.75, credence 0.07, marginal yield 0.15. Considered "contested" because Knuth credibly affirms the claim, but the affirmation rests on plausibility reasoning he himself discounts, and the discourse is lopsided (roughly 88 percent for inequality) with substantial heuristic evidence on that side and none beyond plausibility for equality; §18 asks for the state of the argument, not the existence of dissent. Evaluated all three arguments. No dependents exist, so no notification. Formalization not attempted this pass: Mathlib holds no definitions of P and NP, so a faithful statement would need own definitions of Turing-machine time complexity, which is a substantial project better funded as a formalize item by the mathematics mandate.
Assessed Unsupported
verdict confidence 0.75 · credence 0.07
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.
Updated claim instance
Instance e6472eed-a34b-45af-b39c-2fb1ac9d6559 (https://www.claymath.org/millennium/p-vs-np/): was stance=affirms, confidence=0.9; set stance="poses", confidence=0.9, speaker="Clay Mathematics Institute", publication="Clay Mathematics Institute". Read the full stored page. The Clay Mathematics Institute states P vs NP as an open Millennium Prize problem ("Unsolved"; "one of the outstanding problems in computer science is determining whether..."), and if anything leans toward the problems being genuinely hard ("certainly seem to be of this kind"). It does not assert that P equals NP. The stance was recorded as affirms; the correct stance is poses.
Claim entered the graph