NP-difícil

classe de complexitat

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]

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.

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.