Cook–Levin satisfiability theorem
Boolean satisfiability SAT is NP-complete under polynomial-time many-one reductions.
Key knowledge
Boolean satisfiability SAT is NP-complete under polynomial-time many-one reductions. For each language A∈NP and input x, a polynomial-size formula encodes a polynomial-time accepting computation tableau so that x∈A exactly when that formula is satisfiable; a satisfying assignment itself supplies the NP witness.
Conditions and scope
- SAT inputs are finite Boolean formulas with a reasonable explicit encoding; the reduction depends on the fixed verifier or NTM for A.
- NP-completeness does not prove no polynomial SAT algorithm exists; such an algorithm would imply P=NP.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Lecture 16 slides 3–8: Cook–Levin statement, cell/start/move/accept tableau clauses, both-way interpretation and polynomial construction size.
2026-10-10 · Independent AI editorial review: All241 compact claims, hypotheses, displayed equations/conventions and all596 origin semantic links read; entire241-entry author exact-source inspection matrix and declared limitations reviewed. Prior105 actual inherited Mathematics/Information records read for whole-inventory breadth. Targeted independent primary sections are listed below; this does NOT claim every cited source body or every proof was independently re-read. This is AI reference-content review, not human disciplinary certification, exhaustive textbook reproduction or experimental replication. Receipt: mathematics-information-independent-content-review.1.
Entry details
Permanent link to this entry ↗- Record identity
- info-cook-levin-sat-completeness
- Revision
- university-core.1
- Structured reference record
- University core expansion