SAT to 3-SAT Reduction
You'll learn: How to transform any Boolean satisfiability formula into an equivalent 3-SAT formula, proving that 3-SAT is NP-complete.
The Core Idea
We already know SAT is NP-complete (Cook-Levin Theorem). To prove 3-SAT is also NP-complete, we perform a polynomial-time reduction from SAT to 3-SAT. The trick is converting clauses of any length into clauses with exactly 3 literals, while preserving satisfiability.
Clause Transformation Technique
Given a SAT formula in CNF (clauses with OR-ed literals), we transform each clause based on its size:
Clause with 1 literal: (x₁)
Pad it with dummy variables:
(x₁ ∨ y ∨ z) ∧ (x₁ ∨ y ∨ ¬z) ∧ (x₁ ∨ ¬y ∨ z) ∧ (x₁ ∨ ¬y ∨ ¬z)- These four clauses force
x₁to be true regardless ofyandz
Clause with 2 literals: (x₁ ∨ x₂)
Add one dummy variable:
(x₁ ∨ x₂ ∨ y) ∧ (x₁ ∨ x₂ ∨ ¬y)- Satisfied when either
x₁orx₂is true
Clause with 3 literals: (x₁ ∨ x₂ ∨ x₃)
Perfect! Leave it unchanged.
Clause with k > 3 literals: (x₁ ∨ x₂ ∨ ... ∨ xₖ)
Chain it using new variables y₁, y₂, ..., yₖ₋₃:
(x₁ ∨ x₂ ∨ y₁) ∧ (¬y₁ ∨ x₃ ∨ y₂) ∧ ... ∧ (¬yₖ₋₃ ∨ xₖ₋₁ ∨ xₖ)- This preserves satisfiability: if any original
xᵢis true, the chain remains satisfiable
Why This Works
The transformation runs in polynomial time (linear in the input size), and the new formula is satisfiable if and only if the original is. Since we've reduced SAT to 3-SAT, and SAT is NP-complete, 3-SAT must also be NP-complete.
Key Takeaway: The SAT to 3-SAT reduction uses clause splitting and dummy variables to transform arbitrary-length clauses into exactly 3 literals each, proving 3-SAT's NP-completeness through polynomial-time reduction.