NP-Hard Problems

An NP-hard problem is at least as hard as every problem in NP, but need not itself be in NP.

The definition

A problem is NP-hard if every problem in NP reduces to it in polynomial time. That makes it at least as hard as the hardest NP problems. Unlike NP-complete problems, an NP-hard problem does not have to be a decision problem, and does not have to lie in NP at all.

NP-hard versus NP-complete

• NP-complete: in NP and NP-hard (a decision problem, verifiable)
• NP-hard: at least as hard as NP, but possibly harder or not verifiable
• Every NP-complete problem is NP-hard; not every NP-hard problem is NP-complete

Examples beyond NP

Optimization versions of NP-complete problems are typically NP-hard but not in NP, because their answer is a value or structure rather than a yes/no with a short certificate. The traveling salesman optimization problem (find the shortest tour, not just "is there a tour under length L") is NP-hard.

Harder still

Some NP-hard problems are far above NP. The halting problem is NP-hard yet undecidable, so no algorithm solves it at all. NP-hardness only says "at least as hard as NP"; it places a floor on difficulty, not a ceiling.

Why the label is useful

Proving a new problem NP-hard tells you not to expect an efficient exact algorithm, assuming P is not NP. It redirects effort toward approximation, heuristics, or special cases. The label is a practical warning about where the difficulty lives.

Establishing hardness

You show a problem is NP-hard by reducing a known NP-hard (usually NP-complete) problem to it: transform instances of the known-hard problem into instances of yours so that a solver for yours would solve the hard one. The reduction must itself run in polynomial time to preserve the difficulty comparison.