The Gateway to Engineering Excellence
0 votes
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.

in Theory of Computation by (185 points) 2 7 | 8 views

Please log in or register to answer this question.

Top Users Mar 2019
  1. gatefan

    185 Points

  2. southdelhi

    152 Points

  3. gfjacob

    102 Points

  4. 1995ankur

    100 Points

  5. mohan

    100 Points

₹ 500 Amazon Gift Card for Monthly top user

Recent Badges

Trouper gfjacob
Visitor gfjacob
Regular southdelhi
Verified Human gfjacob
100 Club gfjacob
100 Club 1995ankur
16 questions
0 answers
0 comments
75 users