Questions: NP-Completeness and Cook-Levin Theorem

Question 1

Which of the following best describes what it means for a problem to be NP-complete?

• A. It has no solution
• B. It is in NP and every problem in NP reduces to it in polynomial time
• C. It cannot be solved by any deterministic algorithm
• D. It can only be solved in exponential time

Answer: (B)

NP-completeness requires two things: (1) the problem is in NP — a proposed solution can be verified in polynomial time — and (2) every problem in NP reduces to it in polynomial time, making it at least as hard as any NP problem. It does not mean unsolvable; it means no polynomial-time deterministic algorithm is known.

Question 2

Because no polynomial-time algorithm has ever been found for any NP-complete problem, it has been proven that P ≠ NP.

• T. True
• F. False

Answer: False

The absence of a known polynomial-time algorithm does not constitute a mathematical proof that none exists. P ≠ NP is one of the most famous open problems in mathematics — the Clay Millennium Prize Problem. We strongly believe NP-complete problems are intractable, but 'conjectured' and 'proven' are fundamentally different things in theoretical computer science.

Question 3

Why does finding a polynomial-time algorithm for any single NP-complete problem imply that P = NP?

Model answer: Every problem in NP reduces to every NP-complete problem in polynomial time. So if you can solve one NP-complete problem in polynomial time, you can solve any NP problem in polynomial time by first applying the polynomial reduction and then running the polynomial algorithm. That means NP ⊆ P, and since P ⊆ NP already, P = NP.

The reduction structure is the key: NP-completeness means every NP problem is 'no harder than' the NP-complete problem, up to polynomial overhead. A poly-time solution to the NP-complete problem, composed with poly-time reductions from all other NP problems, yields poly-time algorithms for all of NP. The entire class collapses.