The Gateway to Computer Science Excellence
+10 votes

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

  1. There is no polynomial time algorithm for $\pi_A$.

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

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

  4. $\pi_A$ may be undecidable.

in Theory of Computation by Veteran (52.2k points)
recategorized by | 1.7k views

1 Answer

+18 votes
Best answer

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.

by Active (3.5k points)
edited by

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

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


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,370 users