NP-difficile
Ne doit pas être confondu avec un problème NP-complet.
Un problème NP-difficile est, en théorie de la complexité, un problème appartenant à la classe NP-difficile, ce qui revient à dire qu'il est au moins aussi difficile que les problèmes les plus difficiles de la classe NP.
Ainsi, un problème H est NP-difficile, si tout problème L de la classe NP peut être réduit en temps polynomial à H[1].
Si un problème NP-difficile est dans NP, alors c'est un problème NP-complet. Donc tous les problèmes NP-complets sont NP-difficiles.
Références[modifier | modifier le code]
- D. E. Knuth, « Postscript about NP-hard problems », ACM SIGACT News, vol. 6, no 2, , p. 15–16 (ISSN 0163-5700, DOI 10.1145/1008304.1008305, lire en ligne, consulté le )
