Let πA be a problem that belongs to the class NP. Then which one of the…
GATE · 2009 · CS
Let π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 πA.
- B.
If πA can be solved deterministically in polynomial time, then P = NP.
- C.
If πA is NP-hard, then it is NP-complete.
- D.
πA may be undecidable.
Attempted by 143 students.
Sign up free to check your answer
Sign up freeLoading lesson…