NP-Hard

The NP-Hard class is one of the foundational categories of computational complexity theory and captures problems to which every problem in NP can be reduced in polynomial time. The concept was established by Cook (1971), who showed Boolean satisfiability (SAT) is NP-complete, and by Karp (1972), who proved twenty-one combinatorial problems NP-complete via polynomial-time reductions, anchoring the category in practical OR. A problem that is both in NP and NP-Hard is NP-Complete; if a problem is not in NP it may still be NP-Hard (e.g. the optimization version of TSP). Classic NP-Hard problems include the travelling salesman (TSP), knapsack, graph coloring, set covering, vehicle routing, job shop scheduling, makespan minimization, bin packing, and many mixed-integer programming (MIP) formulations. The P = NP question remains an open mathematical problem; in practice every known exact algorithm for NP-Hard problems takes exponential time in input size. This has driven the development of heuristics, metaheuristics, and approximation algorithms. Garey and Johnson (1979) is the reference for NP-completeness proofs. NP-Hard classification of a problem is a critical signal for practitioners to abandon the expectation of direct exact solution and instead choose relaxation, decomposition, or heuristic approaches.