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.

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

"defn. of NP class, there is no deterministic polynomial time algo"

We should not say like that. Definition says there is "non-deterministic" polynomial time algorithm. It doesn't say there doesn't exist "deterministic" polynomial time algorithm. Otherwise P won't be inside NP. 

---

yes. My bad . basically whether there is any deterministic polynomial time algo for all NP problems , or not,  is again open problem

---

why is B false?

---

because the problem might be in P itself. so by solving in (deterministically ) polynomial time we can't say P=NP

---

A problem in NP, means there exists a non-deterministic polynomial time algorithm for it. Now, if someone gives a polynomial algorithm for it, it becomes a member of P- it can no way say P = NP, as this has nothing to do with other problems in P or NP. 

For example, prime factorization was in NP, and recently a polynomial time algorithm was derived for it- so it became a member of P. 

If a polynomial time algorithm is made for any NPC problem, the P = NP = NPC, because that is how NPC is defined and that is the importance of NPC. 

---

@arjun sir,

Can we say that problems in NP are having polynomial verification algorithms for which we can have non deterministic polynomial time algo./

---

if any problem in np is solved  In a polynomial time, then we can say p=np, so B is also true?

---

^No. Then that problem just moves to $P$ class. But this is true for NPC class.

---

sir,

if a np problem(A) can solved in polynomial time,then all other np problems can able polinomially time reducible to A,?

---

No. How can that work? In fact many problems in NP get solved in polynomial time and they just get moved to $P$. Also any $P$ problem is also in $NP$.

---

THANKS SIR,WHERE CAN I STUDY ABOUT NP COMPLETENESS CORRECTLY.?

---

what a nice point,,, arjun sir i was searching this point and finally i find it

---

@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.