GATE Papers >> CSE >> 2009 >> Question No 14

Let ${\mathrm{\pi }}_{\mathrm{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 ${\mathrm{\pi }}_{\mathrm{A}}$.   
• (B)  If ${\mathrm{\pi }}_{\mathrm{A}}$ can be solved deterministically in polynomial time, then P = NP.   
• (C)  If ${\mathrm{\pi }}_{\mathrm{A}}$ is NP-hard, then it is NP-complete.   
• (D)  ${\mathrm{\pi }}_{\mathrm{A}}$ may be undecidable.