GATE CSE 2009 | Question: 14

Question

Let $\pi_A$ be a problem that belongs to the class NP. Then which one of the following is TRUE?

• A. There is no polynomial time algorithm for $\pi_A$.

• B. If $\pi_A$ can be solved deterministically in polynomial time, then P = NP.

• C. If $\pi_A$ is NP-hard, then it is NP-complete.

• D. $\pi_A$ may be undecidable.

Comments

If a problem is both NP hard and NP, then it is NP Complete.

---

@Kabir5454

does NP  is in syllabus.

---

@Overflow04 No

Answer 1

A problem which is in P, is also in NP- so, A is false. If problem can be solved deterministically in Polynomial time, then also we can't comment anything about P=NP, we just put this problem in P. So, B also false. C is TRUE because that is the definition of NP-complete.

D is false because all NP problems are not only decidable but decidable in polynomial time using a non-deterministic Turing machine.

Comments

@Arjun sir

we can surely say that if L in NPC and L is polynomial time reducible, then we can only say that P = NP , but still we can't say about P= NP= NPC, i have never found anything like this in CLRS ? NPC still a class of problems that would be proper subset of NP but not equal to P, isn't it ?

---

$\pi _{A}\ is\ (NP+ NPH)=NPC$

---

Cleary problem A is  NP-hard But it is not NP-complete so all the options are incorrect.