GATE IT 2006 | Question: 10

Question

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

Answer 1

(B) A problem in NP becomes NPC if all NP problems can be reduced to it in polynomial time. This is same as reducing any of the NPC problem to it. 3-SAT being an NPC problem, reducing it to a NP problem would mean that NP problem is NPC.

http://gatecse.in/wiki/NP,_NP_Complete,_NP_Hard

Comments

@Arjun sir.. have a look at option (D)... this is also correct..

(Some problem in NP) <= (the given problem, which is known to be NP)..

---

No. For D to be correct "some problem in NP" has to be replaced by "all problems in NP".