NP-hard

A problem is NP-hard if every problem in the complexity class NP can be reduced to it in polynomial time. This means that an NP-hard problem is at least as hard as the hardest problems in NP — if you could solve an NP-hard problem efficiently, you could solve all problems in NP efficiently. The term does not require the problem itself to be in NP; NP-hard problems may be strictly harder, belonging to classes like PSPACE or EXPTIME, or they may be optimization problems whose decision versions are in NP.

The concept of NP-hardness, introduced by Stephen Cook and Richard Karp in the early 1970s, transformed theoretical computer science by providing a rigorous framework for identifying problems that are likely intrinsically intractable. Before Cook's theorem and Karp's twenty-one NP-complete problems, the difficulty of problems like the traveling salesman problem, Boolean satisfiability, and graph coloring was suspected but not proved. Afterward, it was established that these problems are all computationally equivalent: solving any one of them efficiently would solve them all.

The Structure of NP-Hardness

NP-hardness is defined through polynomial-time reductions. A problem A is NP-hard if for every problem B in NP, there exists a polynomial-time computable function f that maps instances of B to instances of A, such that B's answer is "yes" if and only if A's answer on f(x) is "yes." This definition makes no reference to the difficulty of solving A directly; it refers only to the existence of reductions from all NP problems.

The most famous subclass of NP-hard problems is NP-complete: problems that are both NP-hard and in NP. SAT, 3-SAT, the traveling salesman problem, maximum clique, and vertex cover are all NP-complete. These problems have the remarkable property that they are universal for NP: any problem in NP can be encoded as an instance of any NP-complete problem, with only polynomial overhead.

NP-Hardness in Practice

The theoretical definition of NP-hardness is worst-case: a problem is NP-hard if it is hard on at least some instances. But in practice, many NP-hard problems are solvable efficiently on typical instances. The average-case complexity of NP-hard problems often differs dramatically from their worst-case complexity. SAT solvers, for instance, routinely solve industrial instances with millions of variables, even though SAT is NP-complete.

This gap between worst-case theory and practical performance has motivated the study of tractable