1.7k 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.

recategorized | 1.7k views

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
+4

"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?
+3
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
0

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

0

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