Which of the following statements about NP-Hard and NP-Complete problems is correct?
Options
-
A.
Every NP-Hard problem must belong to NP
-
B.
Every NP-Complete problem is NP-Hard
-
C.
Every problem in P is NP-Complete
-
D.
More than one of the above
-
E.
None of the above
Correct Answer (Detailed Explanation is Below)
B.
Every NP-Complete problem is NP-Hard
Detailed Explanation
- NP-Hard: A problem at least as hard as every problem in NP under polynomial-time reductions.
- NP-Complete: Problems that are both NP-Hard and members of NP.
- Important Difference: NP-Hard problems need not belong to NP.
- Exam Shortcut: NP-Complete is a subset of NP-Hard.
