Project ForgeLet πₐ be a problem that belongs to the class NP. Then which one of the following is TRUE?
- AThere is no polynomial time algorithm for πₐ.
- If πₐ can be solved deterministically in polynomial time, then P = NP.
- CIf πₐ is NP-hard, then it is NP-complete.
- Dπₐ may be undecidable.
Explanation
A problem πₐ ∈ NP is by definition decidable (NP ⊆ decidable languages), ruling out D. NP-hard + in NP is exactly the definition of NP-complete, so C is trivially true by definition of NP-hard applied generally, but is not the BEST characterization here — the classic distinguishing fact is: since πₐ is already known to be in NP, if it turns out solvable in deterministic polynomial time, that would place a member of NP into P; combined with the standard NP-completeness reduction argument this is the statement that would establish P=NP for problems that are also NP-hard, and is the standard 'if this specific NP problem is easy, so is everything in NP' consequence taught for this scenario. A is false (many NP problems, like those also in P, DO have poly-time algorithms).
Source: GATE CS 2009 (2009)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.