Cook–Levin theorem

E512972

NP-completeness theorem theorem in computational complexity theory

The Cook–Levin theorem is a foundational result in computational complexity theory that established the Boolean satisfiability problem (SAT) as the first NP-complete problem, launching the theory of NP-completeness.

Jump to: Surface forms Statements Referenced by

Observed surface forms (4)

Surface form	Occurrences
Boolean satisfiability problem	1
Cook’s 1971 NP-completeness paper	1
Cook’s theorem	1
SAT is NP-complete	1

Statements (48)

Predicate	Object
instanceOf	NP-completeness theorem ⓘ theorem in computational complexity theory ⓘ
appliesTo	decision version of Boolean satisfiability ⓘ
assumesModel	Turing machine model of computation ⓘ
complexityClassInvolved	NP NERFINISHED ⓘ
concernsComplexityMeasure	time complexity ⓘ
concernsDecisionProblems	yes ⓘ
coreIdea	simulate computation tableau of a nondeterministic Turing machine with a Boolean formula ⓘ
establishes	Boolean satisfiability problem is NP-complete NERFINISHED ⓘ SAT is NP-complete NERFINISHED ⓘ
field	computational complexity theory NERFINISHED ⓘ theoretical computer science ⓘ
firstNPCompleteProblem	Boolean satisfiability problem NERFINISHED ⓘ SAT NERFINISHED ⓘ
formalizes	encoding of nondeterministic Turing machine computations as SAT instances ⓘ
historicalSignificance	first formal NP-completeness result ⓘ
implies	every problem in NP is polynomial-time reducible to SAT ⓘ
importanceLevel	foundational in complexity theory ⓘ
independentlyProvedBy	Leonid Levin NERFINISHED ⓘ
influenced	P versus NP problem research ⓘ development of complexity theory ⓘ
introducedConcept	NP-completeness ⓘ
isBasisFor	classification of many NP-complete problems ⓘ
language	mathematics of computation NERFINISHED ⓘ
launched	theory of NP-completeness NERFINISHED ⓘ
mainResult	Boolean satisfiability problem is NP-complete ⓘ
namedAfter	Leonid Levin NERFINISHED ⓘ Stephen Cook NERFINISHED ⓘ
originallyProvedBy	Stephen Cook NERFINISHED ⓘ
originalPaperTitle	The Complexity of Theorem-Proving Procedures NERFINISHED ⓘ
problemDomain	decision problems over strings ⓘ
problemTypeInvolved	Boolean satisfiability problem ⓘ SAT ⓘ
proofTechnique	polynomial-time encoding of computations into Boolean formulas ⓘ
publishedIn	Proceedings of the Third Annual ACM Symposium on Theory of Computing NERFINISHED ⓘ
relatedConcept	Boolean formula ⓘ NP-complete problem ⓘ P versus NP problem ⓘ nondeterministic Turing machine ⓘ polynomial-time reduction ⓘ
showsHardnessFor	all problems in NP ⓘ
showsSATIs	NP-hard ⓘ in NP ⓘ
standardReferenceIn	NP-completeness textbooks ⓘ
status	proven ⓘ
usedToProve	NP-completeness of other problems via reductions from SAT ⓘ
usesReductionType	polynomial-time many-one reduction ⓘ
yearProved	1971 ⓘ

Referenced by (8)

Full triples — surface form annotated when it differs from this entity's canonical label.

"The Complexity of Theorem-Proving Procedures" → alsoKnownAs → Cook–Levin theorem ⓘ

subject surface form: The Complexity of Theorem-Proving Procedures

this entity surface form: Cook’s 1971 NP-completeness paper

NP-completeness → firstNPCompleteProblem → Cook–Levin theorem ⓘ

this entity surface form: Boolean satisfiability problem

NP-completeness → firstNPCompleteProof → Cook–Levin theorem ⓘ

P versus NP problem → formalizedIn → Cook–Levin theorem ⓘ

this entity surface form: Cook’s theorem

P, NP, and NP-Completeness: The Basics of Complexity Theory → mainTopic → Cook–Levin theorem ⓘ

P versus NP problem → relatedConcept → Cook–Levin theorem ⓘ

"The Complexity of Theorem-Proving Procedures" → relatedConcept → Cook–Levin theorem ⓘ

subject surface form: The Complexity of Theorem-Proving Procedures

"The Complexity of Theorem-Proving Procedures" → result → Cook–Levin theorem ⓘ

subject surface form: The Complexity of Theorem-Proving Procedures

this entity surface form: SAT is NP-complete