Questions: Reductions for Proving NP-Completeness

Question 1

A researcher proves that problem SUBSET-SUM is NP-complete by exhibiting a polynomial-time reduction from 3-SAT to SUBSET-SUM. What does this reduction establish about SUBSET-SUM?

• A. SUBSET-SUM is in P, since the reduction converts hard instances into easy ones in polynomial time
• B. SUBSET-SUM is at least as hard as 3-SAT — any efficient algorithm for SUBSET-SUM could be used to solve 3-SAT efficiently
• C. 3-SAT is at least as hard as SUBSET-SUM, confirming that 3-SAT is harder than previously thought
• D. The reduction proves SUBSET-SUM is undecidable because 3-SAT is undecidable

Answer: (B)

A reduction from A to B establishes that B is at least as hard as A — hardness flows from the source problem (3-SAT) to the target (SUBSET-SUM). The logic is: the reduction converts any 3-SAT instance into a SUBSET-SUM instance in polynomial time, such that a yes-instance maps to a yes-instance. If you had an efficient solver for SUBSET-SUM, you could use this conversion to solve 3-SAT efficiently. Since we believe 3-SAT cannot be solved efficiently, SUBSET-SUM cannot be either. This direction — hardness flowing TO the target — is the most counterintuitive aspect of reductions and the most commonly confused.

Question 2

When proving a problem L is NP-complete, why is it essential to show both that L ∈ NP AND that a known NP-complete problem reduces to L?

• A. Because NP-completeness means L is solvable in polynomial time by a nondeterministic machine, which requires verifying both properties
• B. Because NP-hardness alone would only show L is at least as hard as NP-complete problems, but L might be undecidable rather than in NP
• C. Because NP-completeness is defined as the intersection of NP (verifiable in polytime) and NP-hardness; omitting either step leaves the proof incomplete
• D. Because the reduction only establishes hardness if the source problem is in NP, not just NP-hard

Answer: (C)

NP-completeness means the problem is both in NP (a proposed solution can be verified in polynomial time) AND NP-hard (at least as hard as every problem in NP). Showing only NP-hardness (that a known NP-complete problem reduces to L) leaves open the possibility that L is undecidable or harder than NP — HALT is NP-hard but not in NP. The NP membership step ensures L is in the right complexity class: hard but still verifiable. Both steps are logically necessary for the complete NP-completeness argument.

Question 3

A polynomial-time reduction from problem A to problem B shows that A is at least as hard as B.

• T. True
• F. False

Answer: False

This reverses the direction of hardness propagation — the most common error in reasoning about reductions. A reduction from A to B (written A ≤_p B) shows that B is at least as hard as A, not the other way around. The logic: the reduction converts A-instances into B-instances. An efficient B-solver, combined with this conversion, yields an efficient A-solver. Therefore, B is at least as useful as A for solving computational problems — B is at least as hard. The reduction arrow points FROM A TO B; hardness flows FROM A UP TO B.

Question 4

In the 3-SAT to Clique reduction, a satisfying assignment for a k-clause formula corresponds to a clique of size k in the constructed graph.

• T. True
• F. False

Answer: True

The reduction builds a graph where each clause contributes three nodes (one per literal), and edges connect nodes from different clauses whose literals are non-contradictory. A satisfying assignment sets at least one literal true per clause. Selecting one true literal per clause gives k nodes — one from each clause — all in different clause-groups. Because any two selected literals from different clauses are non-contradictory (they're both true under the assignment), all pairs are connected by edges. This forms a k-clique. The converse direction (k-clique implies satisfying assignment) verifies the other direction of the equivalence, completing the reduction.

Question 5

Explain the direction of hardness propagation in polynomial-time reductions: if A reduces to B, which problem is shown to be at least as hard, and why?

Model answer: If A reduces to B (A ≤_p B), then B is shown to be at least as hard as A. The reason: the reduction is a polynomial-time function that converts any instance of A into an instance of B, such that yes-instances map to yes-instances and no-instances map to no-instances. If you had an efficient solver for B, you could prepend the reduction to obtain an efficient solver for A. Therefore, solving B is at least as powerful as solving A — B is at least as hard. The arrow goes from A to B, but hardness flows in the opposite direction: from A up to B.

This counterintuitive direction is the source of most errors in complexity proofs. Students often think 'A reduces to B means A is harder because it needs B to solve it.' But the correct interpretation is: 'A reduces to B means B can simulate A — B is at least as expressive and at least as hard.' For NP-completeness proofs, you want to show your target problem is hard, so you reduce FROM a known-hard problem TO your target, establishing that your target is at least as hard as the known-hard problem.