1 · The reduction's central trick · digit positions
SUBSET-SUM = {⟨S, t⟩ : S has a subset summing to t}. We prove SUBSET-SUM NP-complete by reducing 3SAT to it (Sipser §7.5). The trick is one of the most beautiful in the chain: each digit position in a base-10 number encodes a separate constraint, so summing numbers digit-by-digit checks all constraints simultaneously.
Construction · f(⟨φ⟩) = ⟨S, t⟩
For a 3CNF φ with n variables and m clauses:
- Layout: each number has n + m digits — n variable positions, m clause positions.
- For each variable xi: two numbers, one for xi = true, one for xi = false. The variable position i has digit 1; clause positions get a 1 in each clause this literal satisfies.
- Slack numbers: for each clause, two slacks of value 1 and 2 in its position (or four slacks of value 1, depending on the variant). They absorb the difference between "clause has 1 true literal" and "clause has 3."
- Target t: digit 1 in each variable position (exactly one of the two variable-numbers chosen), digit 3 in each clause position (clause covered, plus slack).
Two key invariants make this work:
- Variable positions force a choice. Both variable-numbers for xi have digit 1 in position i. To reach target 1, the subset must include exactly one. That's the assignment.
- Clause positions count satisfaction. A clause position's digit equals the number of chosen literals satisfying it. With slacks padding up to 3, the target of 3 is reachable iff the clause has ≥ 1 true literal — iff the clause is satisfied.
2 · Animated demo · auto-plays · loops
4 · Pitfalls
- Base matters · use base ≥ 4. Each clause column can sum to up to 3 (three literals + slack). In base 10 this never overflows the digit, so no carry. In binary, you'd get carries that corrupt other positions.
- Slacks are per-clause, not global. Each clause gets its own slack numbers (typically two of value 1 each). They're padding to make any clause-sum reachable.
- The values are exponential in n+m. Numbers in S are written in O(n+m) digits, so their values are up to 10n+m. The size of the input (number of digits) is polynomial; the numeric value isn't.
- Pseudo-polynomial dynamic programming doesn't break P = NP. SUBSET-SUM has an O(n·t) DP. But t can be exponential in input size, so the DP runs in pseudo-polynomial time, not polynomial.
5 · Q&A defence notes
Q1. Why base 10 (not binary)?
Each clause column can sum to up to 3 (three literals + slack). Base ≥ 4 avoids carries that would propagate between positions and corrupt the encoding. Base 10 is convenient for humans; any base ≥ 4 works.
Q2. Why slack numbers?
A satisfying assignment may satisfy a clause with 1, 2, or 3 true literals. The clause-column sum could be anywhere from 1 to 3. Slacks padd it up to exactly 3 — without slacks, only fully-saturated clauses would hit the target.
Q3. Size of the reduction?
2n + 2m numbers, each n + m digits ⇒ O((n+m)²) total bits. Polynomial in formula size.
Q4. Is the SUBSET-SUM DP polynomial?
It's O(n · t) where n is set size and t is target — pseudo-polynomial. Not polynomial in input size because t is encoded in O(log t) bits. The DP is fast in practice when t is small.
6 · Where to read more
Sipser: Theorem 7.56 (3SAT ≤p SUBSET-SUM). Lecture notes: Module 5 slide 5. Companion problems: P27 (3SAT → CLIQUE), P28 (CLIQUE → VC), P30 (HAMPATH reduction).