3-SAT
/ three-sat /
3-SAT is SAT with a tidy rule imposed: every clause must contain exactly three literals. So an instance is an AND of clauses, each clause an OR of exactly three variables-or-their-negations, like (x1 OR not x2 OR x3) AND (not x1 OR x3 OR x4) AND .... The question is the same as SAT — can we set the variables to make every clause true at once? — but the uniform shape makes 3-SAT the favourite starting point for hardness proofs, because reductions from a neat, fixed-width formula are much easier to design than from arbitrary tangled logic.
Remarkably, restricting to three literals per clause does NOT make the problem easier: 3-SAT is still NP-complete. (By contrast 2-SAT, with two literals per clause, IS solvable in polynomial time — so three is exactly where the difficulty kicks in.) The proof that 3-SAT is NP-complete reduces general SAT to it by chopping fat clauses down to width 3 using fresh helper variables. A clause with more than three literals, say (a OR b OR c OR d OR e), is rewritten as (a OR b OR y1) AND (not y1 OR c OR y2) AND (not y2 OR d OR e), introducing new variables y1, y2 that chain the original literals together. You can check the rewrite preserves satisfiability: the original clause is satisfiable exactly when the new conjunction is, because the helper variables can always be set to 'pass the buck' along the chain until some original literal is true. Short clauses are padded up to width 3 by duplicating a literal. The whole transformation is polynomial, so SAT <=p 3-SAT, and since SAT is NP-complete, 3-SAT is too.
Why prefer 3-SAT over SAT in practice? Because its rigid, three-literals-per-clause structure gives reductions a predictable scaffold. Almost every classic NP-completeness proof in textbooks starts from 3-SAT: each clause becomes a small gadget (a little graph fragment or arithmetic widget), the three literals map to three choices, and the gadgets are wired so that satisfying the formula corresponds to solving the target problem. The reductions to clique, vertex cover, independent set, graph colouring, Hamiltonian cycle and subset-sum all lean on this. One honest caveat to avoid a tempting wrong inference: the polynomial-time solvability of 2-SAT does NOT extend to 3-SAT — the jump from two to three literals is the genuine boundary between easy and (presumed) hard, a vivid reminder that small changes in a problem's definition can flip its complexity entirely.
Widen-to-3 trace: the long clause (a OR b OR c OR d) becomes (a OR b OR y) AND (not y OR c OR d) with one helper y. If a or b is true, set y = false so the first clause holds and the second is satisfied via c or d only if needed; if instead c or d is true, set y = true so the second clause holds and the first is covered by y. Satisfiability is preserved, and every clause now has width 3.
Any SAT formula becomes an equisatisfiable 3-SAT one using chained helper variables — SAT <=p 3-SAT.
Three is the threshold: 2-SAT is in P (solvable via implication graphs), but 3-SAT is NP-complete. Do not assume bounding clause width makes things easy — it is exactly width 3 where tractability ends, a sharp lesson that tiny definitional changes can flip complexity.