miniatura|Diagrama per les classes P, NP, NP-complet i NP-hard. La part esquerra és vàlida assumint que P≠NP. La part dreta és assumint que P=NP. En teoria de la complexitat, la classe de complexitat NP-difícil (o en anglès, NP-hard) és el conjunt dels problemes de decisió tals que si H és un problema d'aquesta classe, tot problema L de NP es pot transformar en H en temps polinòmic. Es pot veure aquesta classe com el conjunt de problemes com a mínim tan difícils com els NP.
Com a conseqüència de la seva definició, si es troba un algorisme de temps polinòmic que solucioni un problema NP-hard, donaria una solució polinòmica a tots els problemes NP, cosa poc probable, ja que tots es consideren massa difícils.
Com classes similars, la NP de NP-hard vol dir que el problema és acceptat en temps polinòmic per una màquina de Turing no determinista.
Relació amb d'altres classes Els problemes NP-hard no tenen perquè pertànyer a la classe de complexitat NP:
Si P ≠ NP llavors els problemes NP-hard no es poden solucionar en temps polinòmic.
Referències
Categoria:Classes de complexitat