Questions: NP-Completeness

Question 1

Which of the following correctly defines NP-completeness?

• A. A problem is in NP but provably not in P
• B. A problem is in NP and every problem in NP reduces to it in polynomial time
• C. A problem cannot be solved by any algorithm, regardless of time
• D. A problem requires exponential time on all inputs

Answer: (B)

NP-completeness requires two things: membership in NP (solutions are verifiable in polynomial time) and NP-hardness (every NP problem reduces to it in polynomial time). The other options confuse NP-completeness with provable intractability, undecidability, or worst-case exponential behavior — none of which are required.

Question 2

If a problem is NP-complete, it is very difficult to solve — no algorithm exists that produces a correct answer.

• T. True
• F. False

Answer: False

NP-completeness says nothing about the existence of an algorithm — exact exponential-time algorithms exist for every NP-complete problem. The claim is that no *polynomial-time* algorithm is known, and under the assumption P ≠ NP, none exists. Approximation algorithms, heuristics, and special-case solvers are all viable despite NP-completeness.

Question 3

What would it mean for all of computer science if someone discovered a polynomial-time algorithm for 3-SAT?

Model answer: It would prove P = NP, meaning every problem in NP could be solved in polynomial time, since 3-SAT is NP-complete and all NP problems reduce to it.

3-SAT is NP-complete, so a polynomial-time solver for 3-SAT would, via polynomial-time reductions, yield polynomial-time solvers for every problem in NP. This would collapse the P vs. NP distinction and make thousands of currently intractable problems (scheduling, optimization, cryptographic hardness assumptions) tractable.