The Complexity of Theorem-Proving Procedures.¶
Cook, S. A. (1971). The Complexity of Theorem-Proving Procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC), 151-158.
Cited by¶
6 citations across 6 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Complexity
- Cook and Levin (1971) independently showed SAT (the Boolean satisfiability problem) is NP-complete—any problem verifiable in polynomial time can be encoded as SAT in polynomial time—establishing a unifying framework for hardness
This sourceVerified existing and supporting.
Supported in partVerified against the publisher's abstract
Cook's 1971 abstract alone shows every NP recognition problem reduces in polynomial time to the tautology/SAT problem; it says nothing of Levin or a joint 1971 discovery.
“It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology.”
- Cook and Levin (1971) independently showed SAT (the Boolean satisfiability problem) is NP-complete—any problem verifiable in polynomial time can be encoded as SAT in polynomial time—establishing a unifying framework for hardness
- Complexity (Time/Space)
- The polynomial-versus-exponential boundary delineating tractable from intractable problem classes
This sourceIntroduces NP-completeness via the Cook–Levin theorem on SAT; the polynomial-vs-exponential / tractable-vs-intractable boundary — supports D30-141. Verified existing and supporting.
Supported in partVerified against the publisher's abstract
Cook's own abstract gives the polynomial-side frame — polynomial-time reduction and 'polynomial degrees of difficulty' — but never states a polynomial-versus-exponential boundary or a tractable/intractable split.
“From this notion of reducible, polynomial degrees of difficulty are defined”
- The polynomial-versus-exponential boundary delineating tractable from intractable problem classes
- Deductive Reasoning
This sourceIntroduces polynomial-time reduction and NP-completeness, proving SAT NP-complete (the Cook–Levin theorem) and formulating P vs. NP. WebSearch confirmed venue, pages, DOI, and content.
- Integer Linear Programming (ILP)
- In computational complexity, ILP is a canonical NP-hard problem, and much of complexity theory's development traces back to Cook's (1971) introduction of NP-completeness, into which integer-programming hardness was promptly absorbed.
This sourceIntroduces NP-completeness via the Cook–Levin theorem on SAT; the foundational complexity result into which Karp embeds integer programming a year later.
Supported in partVerified against the publisher's abstract
Cook (1971) supplies the NP-completeness/reduction framework via tautologyhood, but its abstract never mentions integer or linear programming; the ILP NP-hardness belongs to Karp (1972).
“It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology.”
- In computational complexity, ILP is a canonical NP-hard problem, and much of complexity theory's development traces back to Cook's (1971) introduction of NP-completeness, into which integer-programming hardness was promptly absorbed.
- Verifier-Prover Asymmetry
- In computational complexity, the class NP is precisely the set of decision problems whose candidate solutions can be verified in polynomial time while finding one is conjecturally super-polynomial, and the P-versus-NP question asks whether the gap is real for these problems.
This sourceDefines NP and the satisfiability problem; verifying a candidate assignment is polynomial while finding one is conjecturally hard.
Supported in partVerified against the publisher's abstract
Cook's abstract supplies the polynomial-time nondeterministic-machine framework behind NP, but it does not state the verifier/prover asymmetry or the P-versus-NP conjecture as the claim words them.
“It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology.”
- In computational complexity, the class NP is precisely the set of decision problems whose candidate solutions can be verified in polynomial time while finding one is conjecturally super-polynomial, and the P-versus-NP question asks whether the gap is real for these problems.
Mechanisms¶
- Constraint-Solver Backsolve
- Many inverse problems are computationally hard — the satisfiability core is NP-complete
This sourceEstablishes satisfiability as an NP-complete problem.
- Many inverse problems are computationally hard — the satisfiability core is NP-complete
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 4 of 6 citations: 4 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:d931bc39f5b4 · see in the full table