Reducibility
Glossary Contents
← Ch X
Chapter XI 3-Satisfiability
Ch XII →
  1. 31 — Three is enough
  2. 32 — WalkSAT in Clojure
  3. 33 — Verifying the JVM
Chapter XI

3-Satisfiability

Restrict SAT to clauses of at most three literals. Still NP-complete. The standard starting point for almost every reduction in the literature.

31

Three is enough

Two literals is easy. Three is everything.

Three-SAT is SAT restricted so each clause has at most three literals:

φ=j=1⋀m​(ℓj,1​∨ℓj,2​∨ℓj,3​).(1)

The form (1) is still NP-complete (Karp), and in fact most modern reductions go through 3-SAT rather than general SAT — the fixed clause width simplifies gadget construction.

The 2-SAT version — same as (1) but with two literals per clause — is in P, solvable in linear time via the strongly-connected components of the implication graph. The boundary between 2 and 3 is one of complexity theory's sharpest cliffs:

2-SAT∈P,3-SAT NP-complete.(2)

(2) is the reason 3-SAT motivates entire industries: modern CDCL solvers, the Lasserre hierarchy, the Unique Games Conjecture.

Figures, in plain terms
(1)

Same shape as the SAT figure in chapter 1, with one restriction: every clause has exactly three literals.

φ still names the formula, ⋀ is still the big-AND repeated m times, and the parentheses still hold one clause.

Inside the clause, the OR is now spelled out explicitly with three named slots: ℓ_{j,1} ∨ ℓ_{j,2} ∨ ℓ_{j,3}. The double subscript means "literal i in clause j" — the i picks which of the three positions, the j picks which clause.

Every literal slot is still a variable or its negation, like before. The only change from chapter 1 is the fixed clause width.

(2)

Two complexity classes named side by side.

P is the class of problems solvable in polynomial time. NP-complete problems are the hardest in NP — every NP problem reduces to them, and we don't know how to solve any of them in polynomial time.

The ∈ symbol is the in-set notation again: "2-SAT ∈ P" reads "2-SAT belongs to P."

The figure is a complexity-theoretic cliff edge: drop the literal count from 3 to 2, and the problem moves from intractable (probably) to tractable (definitely, linear time). The boundary lives between these two adjacent integers.

In plain terms

Same as SAT, but every rule mentions at most three things. Surprisingly, this restriction doesn't make the problem easier — three is still enough to encode every hard problem we know about.

Scan to come back to page 31

← 30 PCB drilling and 3D printing
1/3 · 31/63
32 WalkSAT in Clojure →