P32 · SAT self-reducibility

🔊 Listen

1 · Search-to-decision · the surprising self-reducibility

Suppose someone gave you a SAT decider — a procedure that on input φ returns yes/no without telling you the satisfying assignment. Can you use it to find a satisfying assignment? Surprisingly, yes — in only n + 1 calls to D.

Self-reducibility algorithm

on input φ with variables x₁, ..., xₙ:
  if not D(φ): output "UNSAT" and halt
  for i = 1 to n:
    let φ' = φ with xᵢ = TRUE substituted
    if D(φ'):  set xᵢ = TRUE,  φ := φ'
    else:      set xᵢ = FALSE, φ := φ|{xᵢ = FALSE}
  output (x₁, ..., xₙ)

Key insight: substituting x_i = TRUE shrinks the formula by one variable. If the result is still satisfiable, we've found a witness with x_i = TRUE somewhere; if not, x_i = FALSE must work. Either way, the residual formula has one fewer variable. After n iterations all variables are fixed, and the output is a satisfying assignment.

Why it matters

If P = NP, then SAT decision is in P. By self-reducibility, SAT search is also in P — we can actually find satisfying assignments fast, not just say whether they exist. This argument collapses search-to-decision for SAT (and more generally for all NP-complete problems with self-reduction structure).

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Q&A defence notes

Q1. Why does the decider on φ|_x=T tell us x's value?
If D says φ|_x=T is SAT, there's a satisfying assignment with x=T; set x=T. Otherwise the original must have a satisfying assignment with x=F.
Q2. How many calls to D?
n + 1 (one initial check, then n per-variable fixings). Polynomial in the original formula size.
Q3. Does this work for other NP-complete problems?
Yes — SAT's self-reducibility is the canonical pattern. Analogous tricks work for HAMPATH (peel one vertex at a time), CLIQUE (test "is there a clique containing this vertex?"), and most natural NP-complete problems. There are pathological NP-complete problems that aren't self-reducible, but they're contrived.
Q4. Why is this called "self-reducibility"?
Because the algorithm reduces the SAT search problem to multiple instances of SAT decision — a problem reducing to itself (or to a smaller instance of itself). The "self" emphasises that we use the same problem to solve a richer version of it.
Q5. What's the punchline for P vs NP?
If P = NP, then for every NP-complete problem, we can not only decide but also find witnesses in polynomial time. So a P = NP world would be radically different — cryptography, optimisation, theorem-proving all transformed.

🔊 Listen

4 · Pitfalls

Self-reducibility uses the decider as an oracle, not as code. We make black-box calls D(φ'). We don't peek inside.
The residual formulas shrink, not the variable list of the original. Each call passes a smaller formula. n + 1 calls means at most n + 1 oracle invocations, each on poly-size input.
This is a Turing reduction, not a many-one reduction. We make multiple oracle queries with results that affect later queries.

🔊 Listen

5 · Where to read more

Sipser: §7.4 (NP, discussion of search vs decision). Lecture notes: Module 5 slide 6. Companion problems: P22 (SAT interactive), P14 (Rice — for the contrast).