Question

A problem in NP is NP-complete if

• A. It can be reduced to any other problem in NP in polynomial time
• B. It can be reduced to the 3-SAT problem in polynomial time
• C. Some problem in NP can be reduced to it in polynomial time
• D. The 3-SAT problem can be reduced to it in polynomial time

Answer 1

The correct option is B It can be reduced to the 3-SAT problem in polynomial time

3-SAT being an NPC problem, reducing NP problem to 3-SAT would mean that NP problem is NPC.