- [[Traveling Sales Problem Optimization Version (TSP-OPT)]] - precise definition: problem $A$ is NP hard if $\exists$ a [[NP Complete Problems|NP complete problem]] that reduces to $A$ in polynomial time - any problem that is at least as hard as NP complete problems - NP hard problems don't have to be in NP, & they don't have to be decision problems - NP hard problems don't need to be computable - an example of a NP hard problem is the halting problem - to prove that a problem is NP hard, you can reduce a NP complete problem to your problem https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard https://cs.stackexchange.com/questions/65655/is-every-np-hard-problem-computable