A problem in NP is NP-complete if
2006
A problem in NP is NP-complete if
- A.
It can be reduced to the 3-SAT problem in polynomial time
- B.
The 3-SAT problem can be reduced to it in polynomial time
- C.
It can be reduced to any other problem in NP in polynomial time
- D.
Some problem in NP can be reduced to it in polynomial time
Attempted by 44 students.
Show answer & explanation
Correct answer: B
Definition: A problem is NP-complete if it is in NP and every problem in NP can be reduced to it in polynomial time.
Key fact: Because 3-SAT is a known NP-complete problem, showing a polynomial-time reduction from 3-SAT to a problem in NP is sufficient to prove that problem is NP-complete.
Why the correct statement is correct: If the 3-SAT problem can be reduced to the given problem in polynomial time and the given problem is in NP, then the given problem is NP-hard and in NP, so it is NP-complete.
Why the other statements are incorrect:
The statement that the problem can be reduced to 3-SAT (i.e., reducing the problem to 3-SAT in polynomial time) is the reverse direction and does not establish NP-hardness.
The statement that the problem can be reduced to any other problem in NP is also the wrong direction; NP-complete means other problems reduce to it, not that it reduces to others.
The statement that some problem in NP can be reduced to it is too weak. To show NP-hardness you need reductions from all problems in NP or from a known NP-complete problem such as 3-SAT.
A video solution is available for this question — log in and enroll to watch it.