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.

Type

Conference paper

Intellectual base

Primary research

Year

1971

DOI

10.1145/800157.805047

Link

https://doi.org/10.1145/800157.805047

Cited from

computer_science, mathematics, operations_research, philosophy, systems_cybernetics

Cited by

5 citations across 5 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.

• 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.

• 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. Bibliography-only; supports the T5 propositional-logic NP-completeness claim.

• 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.

• 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.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:d931bc39f5b4 · see in the full table