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$ is NP-hard, then it is NP-complete
• C. ${\pi }_A$ may be undecidable
  
• D. If ${\pi }_A$ can be solved deterministically in polynomial time, then P = NP

Answer 1

The correct option is B If ${\pi }_A$ is NP-hard, then it is NP-complete

It is given that ${\pi }_AϵNP$

$\therefore If{\pi }_A$ is NP- hard and since it is given that ${\pi }_AϵNP$, this means that ${\pi }_A$ is NP-complete.

$\therefore$ Choice (c) is correct.

Notice that choice (a) is incorrect since as $PϵNP,$ some NP problems are actually P, and hence polynomial time algorithm can exist for this.

Choice (b) is incorrect since, If ${\pi }_A$ can be solved deterministically in polynomial time, it does not generate that P = NP, unless of-course it is additionally known that ${\pi }_A$ is NP-complete.

Choice (d) is incorrect since,
All problems belonging to P or NP have to be decidable.