Let πA be a problem that belongs to the class NP. Then which one of the…
2009
Let πA be a problem that belongs to the class NP. Then which one of the following is TRUE?
Answer: C. If πA is NP-hard, then it is NP-complete. — Answer: If pA is NP-hard, then it is NP-complete. Why: NP-hard means every problem in NP can be reduced to pA in polynomial time. NP-complete problems are…
- 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 118 students.
Show answer & explanation
Correct answer: C
Answer: If pA is NP-hard, then it is NP-complete.
Why: NP-hard means every problem in NP can be reduced to pA in polynomial time. NP-complete problems are exactly those that are both in NP and NP-hard. Since pA is given to belong to NP, NP-hardness implies pA is NP-complete.
Why the other statements are false:
"There is no polynomial time algorithm for pA" — Being in NP does not preclude membership in P; until P vs NP is resolved, we cannot assert that no polynomial-time algorithm exists.
"If pA can be solved deterministically in polynomial time, then P = NP" — A single NP problem being in P does not imply all NP problems are in P. That implication holds only if the problem is NP-hard (i.e., NP-complete).
"pA may be undecidable." — Problems in NP are decidable by nondeterministic polynomial-time machines (or equivalently have polynomial-time verifiers), so they cannot be undecidable.
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Iocl Engineers Officers Grade A Paper 2