NP-difícil

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.[1][2]

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.[3]

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

  1. ↑ Handbook of theoretical computer science. 1st MIT Press pbk. ed. Amsterdam: Elsevier, 1994, ©1990. ISBN 0262720205. 
  2. ↑ Knuth, D. E. «Postscript about NP-hard problems». ACM SIGACT News, 6, 2, 01-04-1974, pàg. 15–16. DOI: 10.1145/1008304.1008305. ISSN: 0163-5700.
  3. ↑ Pierre), Bovet, Daniel P. (Daniel. Introduction to the theory of complexity. Nova York: Prentice Hall, 1994. ISBN 0139153802. 
  • Vegeu aquesta plantilla
Classes de complexitat
Considerades tractables
DLOGTIME  · AC0  · ACC0  · TC0  · L  · SL  · RL  · NL  · NC  · SC  · CC  · P  · P-complet  · ZPP  · RP  · BPP  · BQP  · APX
Suposadament intractables
UP  · NP  · NP-complet  · NP-hard  · co-NP  · co-NP-complet  · AM  · QMA  · PH  · ⊕P  · PP  · ♯P  · ♯P-complet  · IP  · PSPACE  · PSPACE-complet
Considerades intractables
EXPTIME  · NEXPTIME  · EXPSPACE  · ELEMENTARY  · PR  · R  · RE  · ALL
Jerarquia de classes
Families de classes