Stephen Cook and Leonid Levin independently formulated the P versus NP problem in 1971.
3 events · 1 assessment · 1 decision
Structured and assessed
First pass. Decomposed into two novel subclaims (Matcher confirmed neither existed): Cook's 1971 paper introducing NP-completeness and posing the question (requires, importance 0.12, seeded 0.97), and Levin's independent discovery around 1971 with 1973 publication (requires, importance 0.15, seeded 0.9); both left as deferred stubs as settled bedrock. Did not mint nodes for Karp's 1972 notation or Gödel's 1956 letter, since the claim asserts formulation, not sole priority; these are mentioned in prose. Added a second affirming instance (Fortnow, CACM 2022) found while verifying Levin's dating; recorded a reading of the Clay instance (asserts without citation, quote verified verbatim) and an immaterial source map. Importance set to 0.15, contestation 0.1: settled historical attribution. Assessed supported (confidence 0.8, credence 0.85): Cook half documentary; Levin half rests on Trakhtenbrot's survey and Levin's account for the 1971 date, with publication in 1973, so the claim is correct as the discourse reads it but loose on a strict publication-date reading. Canonical form kept: already short, neutral, and in the discourse's direction. No dependents to notify.
Assessed Supported
verdict confidence 0.80 · credence 0.85
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.
Claim entered the graph