En
teoría de la complejidad computacional, la
clase de complejidad NP-hard (o
NP-complejo, o
NP-difícil) es el conjunto de los
problemas de decisión que contiene los problemas
H tales que todo problema
L en
NP puede ser
transformado polinomialmente en
H. Esta clase puede ser descrita como aquella que contiene a los problemas de decisión que son como mínimo tan difíciles como un problema de
NP. Esta afirmación se justifica porque si podemos encontrar un
algoritmo A que resuelve uno de los problemas
H de NP-hard en
tiempo polinómico, entonces es posible construir un algoritmo que trabaje en tiempo polinómico para cualquier problema de
NP ejecutando primero la reducción de este problema en
H y luego ejecutando el algoritmo
A.