Stephen Cook and Leonid Levin independently formulated the P versus NP problem in 1971.
Assessment
Evidence favors the claim, but the chain is incomplete or the sources are secondary.
The standard history of computational complexity credits the P versus NP problem, in its modern form, to two independent discoveries. Stephen Cook's paper "The Complexity of Theorem-Proving Procedures," presented at the ACM Symposium on Theory of Computing in May 1971, defined polynomial-time reducibility, proved that satisfiability is complete for the class now called NP, and asked whether such problems admit polynomial-time algorithms; that Cook's 1971 paper introduced NP-completeness and posed the question is documented by the paper itself and is not disputed. Leonid Levin, working in Moscow with no knowledge of Cook's result, arrived at the same insight in his note "Universal search problems," which lists several search problems to which every search problem reduces. That Levin independently discovered NP-completeness around 1971 is the consensus of the historical literature, resting on Levin's own account and on Trakhtenbrot's 1984 survey of the Soviet "perebor" tradition, which places his results in seminar talks of 1971 before their publication.
The one imprecision in the claim as stated is the date for Levin: his note was published in 1973, and "1971" refers to when the work was done and first presented, not to a dated publication. Sources that give the year 1971 for both (the Clay Mathematics Institute's overview) and sources that date Levin's contribution to 1973 (many textbooks) are describing the same events at different levels of precision. Two further qualifications belong to the wider history without undercutting the attribution: Richard Karp introduced the notation P and NP and the term "NP-complete" in 1972, and Kurt Gödel's 1956 letter to John von Neumann anticipated the question informally, without the framework of reducibility and completeness that made it precise. Read as the discourse reads it, the claim is correct; a reader who needs the publication chronology should note the 1973 date for Levin.
Full reasoning: the evidence and decisions behind this verdict
Two instances, both affirming: the Clay Mathematics Institute's P vs NP page (www.claymath.org/millennium/p-vs-np/), which states the attribution in one uncited sentence, and Lance Fortnow's 2022 Communications of the ACM retrospective "Fifty Years of P vs. NP and the Possibility of the Impossible" (dl.acm.org/doi/fullHtml/10.1145/3460351), which dates Cook's introduction of the problem to 4 May 1971 and describes Levin's 1973 paper as "based on his independent 1971 research." No source found denies either the independence or the rough contemporaneity.
The Cook half is documentary: Cook's paper appears in the proceedings of the third ACM STOC (1971), pp. 151–158, and Cook's own Clay problem description (www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf) recounts that "in 1971 the present author introduced a notion of NP-completeness" and that Karp introduced the P/NP notation a year later. Cook's 1971 paper introduced NP-completeness and posed the P versus NP question therefore stands essentially beyond doubt.
The Levin half is where the precision lies. Levin's "Universal'nye perebornye zadachi" appeared in Problemy Peredachi Informatsii 9(3), 1973, pp. 115–116 (English translation in Problems of Information Transmission 9, pp. 265–266, and a corrected translation appended to Trakhtenbrot's survey). Trakhtenbrot, "A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms," Annals of the History of Computing 6(4), 1984, is the main historical source for the dating of Levin's work to 1971 and for its independence; Wikipedia's Cook–Levin theorem article summarises this as the paper having been "mentioned in talks and submitted for publication a few years earlier" than 1973, and Shen's memoir on Kolmogorov complexity in the USSR (arxiv.org/pdf/1907.05056) corroborates that Levin was circulating the problem in Moscow. Independence is not disputed anywhere in the literature read; Fortnow's blog discussion of the Cook–Levin theorem notes only that Levin's note lacks full definitions and proofs, in the Russian style of the period. The residual uncertainty is that the 1971 date for Levin rests on recollection rather than a dated document, which is why Levin independently discovered NP-completeness around 1971, publishing in 1973 is held at high but not full credence.
Weighing: the claim is true on the reading its sources intend (independent discoveries, both around 1971), and slightly loose on a strict publication-date reading for Levin. The status is supported rather than verified because the Levin date is fixed by secondary historical accounts rather than by a primary dated record, and the credence of about 0.85 reflects mainly that ambiguity of reading rather than any doubt about the substance. What would change the verdict: a dated 1971 or 1972 manuscript or seminar record for Levin's result would move it to verified; evidence that Levin's work postdated knowledge of Cook's would contradict the independence and hence the claim. Gödel's 1956 letter does not bear on the claim, which asserts formulation, not sole priority.
Decomposition
The claims this one rests on directly. ↗︎ opens a subclaim; the map shows how they fit together.
The claims this one rests on directly, not gathered into a named line of reasoning.
- requiresa load-bearing premise: the parent is false without itsteward instructions →Cook's 1971 paper introduced NP-completeness and posed the P versus NP question. ↗︎
- requiresa load-bearing premise: the parent is false without itsteward instructions →Leonid Levin independently discovered NP-completeness around 1971, publishing it in 1973. ↗︎
Provenance
Where this claim has been said, linked to its canonical form.
Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.
Historical note closing the overview of the P vs NP problem.
Asserted without evidence of the source's own. The Clay Institute's overview states the attribution in one sentence with no citation. It compresses the standard history: Cook's paper appeared in 1971, while Levin's independent work, dated by his own account and by Trakhtenbrot's survey to about 1971, was published only in 1973.
On May 4, 1971, computer scientist/mathematician Steve Cook introduced the P vs. NP problem to the world in his paper, "The Complexity of Theorem Proving Procedures." ... In 1973, Leonid Levin, then in Russia, published a paper based on his independent 1971 research that defined the P vs. NP problem.
Opening historical section of a fiftieth-anniversary retrospective on the P versus NP problem; the author distinguishes Cook's 1971 publication from Levin's 1973 publication of independent 1971 research.
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.