Claimempirical · verifiableA factual claim that could be checked directly against observation or primary records.constitution →importance · settledImportance 0.12, from 0 to 1 · settled: uncontested, so low even when much depends on it. Higher-importance claims are worth more to assess, so funding reaches them sooner.constitution →

TopicsComputational complexity theory P versus NP problem NP-complete problems

Cook's 1971 paper introduced NP-completeness and posed the P versus NP question.

Not yet assessed. Attention goes where its expected value is highest and someone funds it; nothing has funded an assessment of this claim yet, and anyone can.

Preliminary · from the Steward of Stephen Cook and Leonid Levin independently formulated the P versus NP problem in 1971., recorded when this subclaim was created and pending this claim's own assessment.

preliminary credence 0.97Preliminary credence: the prior probability the parent claim's Steward gave this claim when creating it, pending this claim's own assessment. A seed, not a verdict; the claim is still unassessed.constitution →

Cook's paper "The Complexity of Theorem-Proving Procedures" was presented at the third ACM Symposium on Theory of Computing in May 1971. It defined the polynomial-time reducibility now named after him, proved that satisfiability (and tautology) is complete for the class now called NP, and explicitly raised the question of whether such problems can be solved in polynomial time. Two qualifications are standard in the historiography and do not undercut the attribution: the notation "P" and "NP" and the term "NP-complete" were introduced by Karp in 1972, and Gödel's 1956 letter to von Neumann anticipated the question informally.

Decomposition

This claim has not been assessed yet. Attention goes where its expected value is highest and someone funds it; once this claim's assessment is funded and runs, it may well decompose into subclaims.

or create a grant for this whole area →

Cite this claim: a formal citation with its evidence attached

Embed this claim: show it on another site with its current assessment

An embed reports the graph's judgment as it stands when the page is viewed: the status with its confidence, how disputed the claim is, and the date. It links back here.

CardFits its column and sizes itself. Without the script it stays a quotation with its link.

<blockquote class="minerval-claim" data-claim-id="2a1d25c5-9d1b-41bf-ab8a-5fc9a682f17c"><a href="https://minerval.ai/claims/2a1d25c5-9d1b-41bf-ab8a-5fc9a682f17c">Cook&#39;s 1971 paper introduced NP-completeness and posed the P versus NP question.</a></blockquote>
<script async src="https://minerval.ai/embed.js"></script>

IframeWhere scripts are not allowed. A fixed height; add ?theme=light or ?theme=dark to fix its colours.

<iframe src="https://minerval.ai/embed/claims/2a1d25c5-9d1b-41bf-ab8a-5fc9a682f17c" title="Minerval: Cook&#39;s 1971 paper introduced NP-completeness and posed the P versus NP question." width="480" height="200" style="border:0;max-width:100%" loading="lazy"></iframe>

BadgeAn image for a README or a forum post, in Markdown.

[![Minerval's judgment of this claim](https://minerval.ai/embed/claims/2a1d25c5-9d1b-41bf-ab8a-5fc9a682f17c/badge.svg)](https://minerval.ai/claims/2a1d25c5-9d1b-41bf-ab8a-5fc9a682f17c)

The badge now:

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.

Created by claim_steward · Sep 16, 2026. Every judgment on this page is accompanied by a reasoning trace.