NP-difícil
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]- ↑ Handbook of theoretical computer science. 1st MIT Press pbk. ed. Amsterdam: Elsevier, 1994, ©1990. ISBN 0262720205.
- ↑ 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.
- ↑ Pierre), Bovet, Daniel P. (Daniel. Introduction to the theory of complexity. Nova York: Prentice Hall, 1994. ISBN 0139153802.
| Considerades tractables | |
|---|---|
| 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 | |
| Jerarquia de classes | |
| Families de classes | |
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
