Equisatisfiable reduction from SAT to 3SAT
Introduce variables for Boolean subformula gates, constrain each gate to agree with its inputs using clauses of at most three literals, and require the output gate true.
Key knowledge
Introduce variables for Boolean subformula gates, constrain each gate to agree with its inputs using clauses of at most three literals, and require the output gate true. This constructs a linear-size equisatisfiable 3CNF formula, showing SAT≤ₚ3SAT and therefore 3SAT is NP-complete.
Conditions and scope
- The original formula's parse tree has an explicit encoding; new variables are fresh and existentially assignable.
- Equisatisfiability is not literal formula equivalence on the enlarged variable set. Clauses of one or two literals may be padded by repeated literals if exactly three positions are required.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Lecture 16 slide 9 gate/subformula construction and 3SAT theorem. Gate equivalence uses truth-table clauses for both directions; padding repeats a literal without changing a clause's value.
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-sat-three-cnf-reduction
- Revision
- university-core.1
- Structured reference record
- University core expansion