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

[modifica]

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

[modifica]
  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. 
Obtingut de «https://ca.wikipedia.org/w/index.php?title=NP-difícil&oldid=31542642»