Multiple choice

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 un decidable.
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Keep practicing — related questions