The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
852 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 (69k points)
recategorized by | 852 views

1 Answer

+9 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 Loyal (3.4k 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./


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

33,687 questions
40,230 answers
114,268 comments
38,795 users