Kerala PSC AP Exam

Question

A problem in NP is NP complete if

A) Some problem in NP can be reduced to it in polynomial time

B) The 3-SAT problem can be reduced to it in polynomial time

C) It can be reduced to any other problems in NP in polynomial time

D) It can be reduced to the 3SAT problem in polynomial time

Comments

But a Prof. told me that if any exam copies a good amount of questions from any book one can go to court and file a case. It is illegal to do so.

---

I have right now closed many questions of this exam. If anyone posts ISRO exam questions here, 70% of them also get closed :)

---

Okay, next GO book I'll add a line many PSC and ISRO questions are taken from this :P

Answer 1

A problem is NP-complete if the problem is both

• NP-hard, and
• in NP.

A can be reduced to B in polynomial time e.g B is more harder than A

To satisfy above two answer should be (B)

in terms of hardness:

NP<NP-complete<NP-hard

Comments

@Arjun sir if 3SAT problem reduces to some problem say P1 in polynomial time means that problem P1 is NP Hard? If problem P1 reduces to 3SAT means P1 is less hard it would belong to NP accordingly ans should be d?

With reference to this question

Please correct me if i am wrong

https://gateoverflow.in/8048/gate2015-2-2