The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
1.3k views

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.

asked in Theory of Computation by Veteran (59.7k points)
recategorized by | 1.3k views

1 Answer

+14 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.

answered by Active (3.5k points)
edited by
+3

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

0
yes. My bad . basically whether there is any deterministic polynomial time algo for all NP problems , or not,  is again open problem
0
why is B false?
+2
because the problem might be in P itself. so by solving in (deterministically ) polynomial time we can't say P=NP
+9

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. 

0
@arjun sir,

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

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

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

if a np problem(A) can solved in polynomial time,then all other np problems can able polinomially time reducible to A,?
0
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$.
0
THANKS SIR,WHERE CAN I STUDY ABOUT NP COMPLETENESS CORRECTLY.?
0
what a nice point,,, arjun sir i was searching this point and finally i find it
Answer:

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

44,494 questions
49,946 answers
165,720 comments
65,911 users