In the context of NP-completeness, what is the term for a problem that is at least as hard as the hardest problems in NP, but might not be in NP itself?
Show answer
NP-hard
A problem is NP-hard if every problem in NP can be reduced to it in polynomial time. If an NP-hard problem is also in the class NP, then it is classified as NP-complete.
Also asked as:
- What term describes a problem that is at least as difficult as the hardest problems in NP, regardless of whether it belongs to NP itself?