11.3

Goal: Reduce any 3-SAT instance F to an equi-satisfiable 4-SAT instance G in polynomial time.

Input: F consists of m clauses C_i = (ℓ_i1 ∨ ℓ_i2 ∨ ℓ_i3).
Construction: For every C_i introduce one fresh variable x_i and replace C_i with the two 4-literal clauses
    D_i,1 = (ℓ_i1 ∨ ℓ_i2 ∨ ℓ_i3 ∨ x_i)
    D_i,2 = (ℓ_i1 ∨ ℓ_i2 ∨ ℓ_i3 ∨ ¬x_i)
Let G be the conjunction of all 2m clauses {D_i,1, D_i,2}. Each clause now contains exactly four literals, so G is a 4-SAT formula.

Equi-satisfiability proof
1. If F is satisfiable, extend the satisfying assignment α of its original variables with arbitrary values for every x_i. Because at least one of ℓ_i1,ℓ_i2,ℓ_i3 is true under α, both D_i,1 and D_i,2 are true, so α satisfies G.
2. Conversely, suppose G is satisfiable by some assignment β.
  • If C_i were false under β on the original literals, then ℓ_i1,ℓ_i2,ℓ_i3 are all false.
  • In that case D_i,1 simplifies to x_i and D_i,2 simplifies to ¬x_i, so at most one can be true—contradicting that β satisfies both.
  • Therefore every original clause C_i is true under β, and β restricted to F’s variables satisfies F.

Complexity: The reduction introduces at most one new variable and two new clauses per original clause, hence runs in O(|F|) time.

Pseudocode
function Reduce3to4SAT(F):
  G ← ∅
  for each clause (a ∨ b ∨ c) in F do
    x ← newVariable()
    G.add( (a ∨ b ∨ c ∨ x) )
    G.add( (a ∨ b ∨ c ∨ ¬x) )
  return G

Since 3-SAT is NP-hard and we have given a polynomial-time reduction 3-SAT ≤_p 4-SAT, it follows that 4-SAT is NP-hard. □

Back to Chapter 11