NP-schwer

Die Klasse NP-schwer (NP-Hard) ist eine Grundkategorie der Komplexitätstheorie und umfasst Probleme, auf die jedes Problem in NP in Polynomialzeit reduziert werden kann. Den Begriff prägten Cook (1971) mit dem Nachweis der NP-Vollständigkeit des Booleschen Erfüllbarkeitsproblems (SAT) und Karp (1972) mit dem Beweis der NP-Vollständigkeit von einundzwanzig kombinatorischen Problemen via Polynomialzeit-Reduktionen, was die Kategorie in der praktischen OR verankerte. Ein Problem, das sowohl in NP als auch NP-schwer ist, heißt NP-vollständig; liegt es nicht in NP, kann es dennoch NP-schwer sein (z. B. die Optimierungsversion von TSP). Klassische NP-schwere Probleme: Travelling Salesman (TSP), Rucksackproblem, Graphfärbung, Set Covering, Vehicle Routing, Job-Shop-Scheduling, Makespan-Minimierung, Bin Packing und viele gemischt-ganzzahlige Programmierformulierungen. Die Frage P = NP ist mathematisch offen; praktisch braucht jeder bekannte exakte Algorithmus für NP-schwere Probleme exponentielle Zeit in der Eingabegröße. Dies hat die Entwicklung von Heuristiken, Metaheuristiken und Approximationsalgorithmen angetrieben. Garey und Johnson (1979) ist die Referenz für NP-Vollständigkeitsbeweise. Die Einstufung NP-schwer signalisiert dem Praktiker, exakte Direktlösung aufzugeben und stattdessen Relaxation, Dekomposition oder heuristische Ansätze zu wählen.