NP-hard Problem

computation

Definition

NP-hard Problem

A problem is called NP-hard if every problem in NP can be reduced to it in polynomial time, i.e.:

$$p\text{ is NP-hard}:⟺\forall q\in \mathrm{NP}:q{\le }_{P}p$$

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

Approximation

Suppose we still want to solve an NP-hard Problem