Questions: NP-Completeness and the Cook-Levin Theorem

Question 1

A researcher wants to prove that the Vertex Cover problem is NP-hard. She constructs a polynomial-time algorithm that transforms any Vertex Cover instance into an instance of 3-SAT. Does this prove NP-hardness of Vertex Cover?

• A. Yes — both are in NP, so reducing Vertex Cover to 3-SAT shows they are equally hard
• B. No — this shows only that Vertex Cover is in NP (or easier); to prove NP-hardness, she must reduce FROM a known NP-hard problem TO Vertex Cover
• C. Yes — 3-SAT is NP-complete, so any problem reducible to 3-SAT inherits NP-completeness
• D. No — Cook-Levin is the only valid proof technique; reductions from other problems are circular

Answer: (B)

The direction of reduction is everything. A reduction FROM problem A TO problem B means: 'If I can solve B, I can solve A,' establishing that B is at least as hard as A. To prove Vertex Cover is NP-hard, you must show every NP problem can be reduced to it — equivalently, reduce FROM a known NP-hard problem TO Vertex Cover. Reducing Vertex Cover TO 3-SAT shows the opposite: Vertex Cover is no harder than 3-SAT, which helps show it is in NP, not that it is NP-hard. Confusing these directions is the single most common error in NP-hardness proofs.

Question 2

A computer scientist discovers a polynomial-time algorithm for 3-SAT. She also knows that every instance of 3-SAT can be converted into an instance of a scheduling problem S in polynomial time. What does this imply for the scheduling problem?

• A. Nothing unexpected — having an efficient algorithm for 3-SAT does not affect other problems
• B. Every problem in NP can now be solved in polynomial time, because any NP problem reduces to 3-SAT, which reduces to S, which is efficiently solvable
• C. Only 3-SAT gains a polynomial-time solution; other NP problems are unaffected
• D. The scheduling problem must be misclassified — no NP-complete problem can have a polynomial-time algorithm unless P = NP

Answer: (B)

The transitive chain of reductions collapses the entire complexity class. Any NP problem X has a polynomial reduction to 3-SAT (because 3-SAT is NP-complete). If 3-SAT further reduces to S, and S is solvable in polynomial time, then X can be solved in polynomial time by composing the reductions. This is why NP-completeness creates an equivalence class: solving any one NP-complete problem efficiently solves all of NP. Option D correctly notes that this would imply P = NP — but that is an implication to be drawn, not a reason to dismiss the hypothetical.

Question 3

NP-hardness implies membership in NP: a problem that is NP-hard should also be in NP.

• T. True
• F. False

Answer: False

NP-hardness and NP-membership are independent properties. 'NP-hard' means every problem in NP reduces to it in polynomial time — the problem is at least as hard as the hardest NP problems. But the NP-hard problem itself need not admit polynomial-time verification (the requirement for NP membership). The halting problem is NP-hard but is undecidable and not in NP. PSPACE-complete problems are NP-hard but not known to be in NP. NP-complete = NP-hard ∩ NP: both conditions must hold simultaneously.

Question 4

Cook-Levin's historical significance is that it provided the first NP-complete problem, enabling all subsequent NP-completeness proofs to reduce from SAT rather than re-encoding Turing machine computations as Boolean formulas from scratch.

• T. True
• F. False

Answer: True

Before Cook-Levin, NP-hardness existed as a concept but had no confirmed instances. The Cook-Levin proof — encoding the entire computation tableau of an NP verifier as a polynomial-size Boolean formula — established that SAT is NP-complete. This bootstrapped an entire research program: subsequent proofs (3-SAT, CLIQUE, Vertex Cover, Hamiltonian Path, hundreds more) needed only a polynomial reduction from SAT or from any already-known NP-complete problem, inheriting the universal reduction property transitively. The Cook-Levin tableau construction had to be done once; every proof after it stands on those shoulders.

Question 5

Why does the direction of a polynomial-time reduction matter when proving NP-completeness, and what does each direction establish?

Model answer: A polynomial-time reduction from A to B (written A ≤_p B) means any instance of A can be transformed into an equivalent instance of B in polynomial time — so if B is efficiently solvable, so is A. This means B is at least as hard as A. To prove problem X is NP-hard, you reduce FROM a known NP-hard problem TO X, establishing that X is at least as hard as something already known to be hard. Reducing in the other direction (from X to a known NP-hard problem) would show X is no harder than the known problem, helping show X is in NP. NP-completeness requires both: membership in NP (polynomial verification) and NP-hardness (a known NP-complete problem reduces to X).

The asymmetry is intuitive once reductions are read as 'X is no harder than Y': X ≤_p Y means X is no harder than Y. To prove something is hard, you need a hard problem that is no harder than your target — i.e., the hard problem reduces to your problem. Confusing the direction is the most common error in NP proofs, because both involve a polynomial-time transformation but the implications run in opposite directions.