Q14

MCQ1 mark, −0.33

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$ can be solved deterministically in polynomial time, then P = NP.

(C)

If $\pi_A$ is NP-hard, then it is NP-complete.

(D)

$\pi_A$ may be undecidable.

Loading…