auch NP-hartes Problem, ein Problem mit der Eigenschaft, daß es für die Komplexitätsklasse C = NP (NP) und Turing-Reduktionen ein C-hartes Problem ist.

Für ein NP-schweres Problem kann es nur dann einen polynomialen Algorithmus (polynomialer Algorithmus) geben, wenn NP=P (NP-Vollständigkeit) ist. Da die NP≠P-Hypothese gut begründet ist, gelten NP-harte Probleme als nicht effizient lösbar.