Questions: Boolean Satisfiability, Cook-Levin, and Reductions

Question 1

A researcher wants to prove that CLIQUE is NP-complete. She has already shown CLIQUE is in NP. Which correctly describes the next step?

• A. Reduce CLIQUE to 3-SAT in polynomial time
• B. Reduce 3-SAT to CLIQUE in polynomial time
• C. Show CLIQUE reduces to SAT, then SAT reduces back to CLIQUE
• D. Show that any algorithm for CLIQUE can directly solve SAT

Answer: (B)

To show NP-hardness, you reduce a *known* NP-complete problem (3-SAT) TO the *target* problem (CLIQUE). This proves CLIQUE is at least as hard as 3-SAT: a polynomial-time algorithm for CLIQUE would immediately yield one for 3-SAT. Option A gets the direction backwards — reducing CLIQUE to 3-SAT only shows CLIQUE is no harder than 3-SAT (i.e., CLIQUE ∈ NP), which you already knew. The direction of reduction is the most common confusion in NP-completeness proofs.

Question 2

The Cook-Levin theorem proves SAT is NP-complete. What does the NP-hardness part of this mean precisely?

• A. SAT cannot be solved in polynomial time
• B. SAT is the hardest problem solvable in polynomial space
• C. Every language in NP can be reduced to SAT in polynomial time
• D. SAT can solve every NP problem without any reduction

Answer: (C)

NP-hardness means every language in NP polynomial-time reduces TO SAT — if you could solve SAT efficiently, you could solve any NP problem by first transforming it into SAT. Cook-Levin establishes this by showing the accepting computations of any nondeterministic polynomial-time TM can be encoded as a satisfiable CNF formula. Crucially, the theorem does not *prove* SAT is intractable (that would require proving P ≠ NP) — it only shows SAT is at least as hard as every other NP problem.

Question 3

If problem A reduces to problem B in polynomial time, and B is in P, then A must also be in P.

• T. True
• F. False

Answer: True

This is the core property that makes polynomial-time reductions useful. If A ≤_p B, you solve any instance of A by: (1) running the polynomial-time reduction to produce a B instance, then (2) running the polynomial-time algorithm for B. The composition of two polynomial-time procedures is polynomial-time, so A ∈ P. This is why NP-completeness is so consequential: if any NP-complete problem is in P, then P = NP, because every NP language reduces to that problem.

Question 4

To prove SUBSET-SUM is NP-complete, it suffices to reduce SUBSET-SUM to 3-SAT in polynomial time.

• T. True
• F. False

Answer: False

This gets the reduction direction backwards — the most common error in NP-completeness arguments. Reducing SUBSET-SUM *to* 3-SAT shows SUBSET-SUM is no harder than 3-SAT (i.e., SUBSET-SUM ∈ NP). To prove NP-hardness, you must reduce *from* 3-SAT *to* SUBSET-SUM: given a 3-SAT formula, construct a SUBSET-SUM instance that is solvable if and only if the formula is satisfiable. That shows any polynomial algorithm for SUBSET-SUM would also solve 3-SAT.

Question 5

Why does the Cook-Levin proof encode a Turing machine's computation as a CNF formula, and what do the variables in that formula represent?

Model answer: To show every NP language L reduces to SAT, the proof takes the nondeterministic polynomial-time TM M for L and constructs a CNF formula that is satisfiable iff M accepts the input. Variables represent the configuration at each time step: the machine's state, head position, and tape cell contents. Clauses enforce that each step follows M's transition function, the initial configuration matches the input, and some accepting state is reached. A satisfying assignment corresponds exactly to an accepting computation history.

The insight is that 'does an accepting computation exist?' is a combinatorial question about a table of configurations, and CNF clauses naturally express local consistency constraints between adjacent table cells. The formula size is polynomial because M runs in polynomial time, making the computation table polynomial-sized. This translation is the conceptual bridge between abstract nondeterministic computation and concrete logical satisfiability.