Let πA be a problem that belongs to the class NP. Then which one of the…

PYQ GATE 2009

Let πA be a problem that belongs to the class NP. Then which one of the following is TRUE?

  1. A.

    There is no polynomial time algorithm for πA.

  2. B.

    If πA can be solved deterministically in polynomial time, then P = NP.

  3. C.

    If πA is NP-hard, then it is NP-complete.

  4. D.

    πA may be undecidable.

Attempted by 162 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…