Course contentsShow
← Computer Science
Lesson 1933 of 2,87243. Complexity TheoryFree lesson

SAT to 3-SAT Reduction

Work through the classic reduction from general SAT to 3-SAT using clause transformation techniques.

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 of y and z

Clause with 2 literals: (x₁ ∨ x₂)

Add one dummy variable:

  • (x₁ ∨ x₂ ∨ y) ∧ (x₁ ∨ x₂ ∨ ¬y)
  • Satisfied when either x₁ or x₂ 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.