Definition
NP-hard Problem
A problem is called NP-hard if every problem in NP can be reduced to it in polynomial time.
NP-complete vs. NP-hard
The primary reason a problem is NP-hard but not NP-complete is that is fails the key requirement being in NP, namely, that a proposed solution (“certificate”) an be verified in polynomial time.
Examples:
- Halting Problem: It’s possible to reduce NP-complete problems, like SAT, to the Halting problem. However, if a program is designated to run forever, there’s no certificate to prove this is a finite amount of time.
- Travelling Salesman Problem