Introduction

Alright, time to zoom in on a superstar of NP-complete problems: 3‑SAT. This is just like SAT, but every clause has exactly three literals. You might think that restricting clause size makes it easier, but nope! 3‑SAT is still NP-complete, and it’s the go-to starting point for reductions in complexity theory.

Problem Statement

A Boolean formula is in 3‑CNF if it’s a conjunction of clauses, each clause having exactly three literals:

$$ f = (ℓ_{1,1} \lor ℓ_{1,2} \lor ℓ_{1,3}) \land (ℓ_{2,1} \lor ℓ_{2,2} \lor ℓ_{2,3}) \land \cdots \land (ℓ_{m,1} \lor ℓ_{m,2} \lor ℓ_{m,3}), $$

where each literal $ℓ_{i,j}$ is either a variable $x_k$ or its negation $\lnot x_k$.

The 3‑SAT decision problem asks:

Is there an assignment to the variables that makes the entire formula $f$ true?

Example

Consider the formula

$$ f = (x \lor \lnot y \lor z) \land (\lnot x \lor y \lor w) \land (\lnot w \lor y \lor \lnot z). $$

Try the assignment $x=\mathrm{True}, y=\mathrm{False}, z=\mathrm{True}, w=\mathrm{False}$:

  • Clause 1: $x \lor \lnot y \lor z = \mathrm{True} \lor \mathrm{True} \lor \mathrm{True} = \mathrm{True}.$
  • Clause 2: $\lnot x \lor y \lor w = \mathrm{False} \lor \mathrm{False} \lor \mathrm{False} = \mathrm{False}.$

That fails, so tweak to $y=\mathrm{True}, w=\mathrm{False}$:

  • Clause 1: still True.
  • Clause 2: $\lnot x \lor y \lor w = \mathrm{False} \lor \mathrm{True} \lor \mathrm{False} = \mathrm{True}.$
  • Clause 3: $\lnot w \lor y \lor \lnot z = \mathrm{True} \lor \mathrm{True} \lor \mathrm{False} = \mathrm{True}.$

All clauses are satisfied, so this instance is satisfiable.

NP-Completeness of 3‑SAT

  1. 3‑SAT is in NP: Given an assignment, checking each of the $m$ clauses takes $O(m)$ time.

  2. Hardness: We reduce from general SAT (or directly from Circuit SAT):

    • Clause size >3: Break a clause $(ℓ_1 \lor ℓ_2 \lor \cdots \lor ℓ_k)$ into a chain of 3‑literal clauses using fresh variables $y_1, y_2, …$:

      $$ (ℓ_1 \lor ℓ_2 \lor y_1) \land (\lnot y_1 \lor ℓ_3 \lor y_2) \land (\lnot y_2 \lor ℓ_4 \lor y_3) \land \cdots \land (\lnot y_{k-3} \lor ℓ_{k-1} \lor ℓ_k). $$

    • Clause size = 2: Duplicate a literal: $(ℓ_1 \lor ℓ_2)$ becomes $(ℓ_1 \lor ℓ_2 \lor ℓ_2)$.

    • Clause size = 1: Duplicate twice: $(ℓ)$ becomes $(ℓ \lor ℓ \lor ℓ)$.

This transformation is polynomial-time and preserves satisfiability, proving 3‑SAT is NP-hard.

Why It Matters

  • Reduction Hub: Many NP-complete problems are shown hard via reductions from 3‑SAT.
  • Benchmark for Solvers: 3‑SAT instances are standard benchmarks for SAT solver performance.
  • Theoretical Core: It crystallizes why even tiny local constraints can lead to global computational difficulty.

Wrap-Up

3‑SAT shows that even a tight syntactic restriction doesn’t ease the NP-complete beast. Next in our series: the Clique Problem and its NP-completeness demonstration!