8 views

Let $π_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 $π_A$.

2. If $π_A$ can be solved deterministically in polynomial time, then P = NP.

3. If $π_A$ is NP-hard, then it is NP-complete.

4. $π_A$ may be undecidable.

| 8 views