Ne doit pas être confondu avec un problème NP-complet.
En théorie de la complexité, un problème NP-difficile est 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],[2].
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.
Exemples
Il existe des problèmes de décision qui sont NP-difficiles mais pas NP-complets, comme le problème d'arrêt. Il s'agit du problème qui demande : « Étant donné un programme et ses entrées, s'exécutera-t-il indéfiniment ?» C'est une question de type oui/non, et c'est donc un problème de décision. Il est facile de démontrer que le problème d'arrêt est NP-difficile mais pas NP-complet. Par exemple, le problème SAT peut être réduit au problème d'arrêt en le transformant en une description de machine de Turing qui essaie toutes les affectations de valeurs de vérité et, lorsqu'elle en trouve une qui satisfait la formule, s'arrête ; sinon, elle entre dans une boucle infinie. Il est également facile de voir que le problème d'arrêt n'est pas NP, car tous les problèmes NP sont décidables en un nombre fini d'opérations, mais le problème d'arrêt, en général, est indécidable.
Il existe également des problèmes NP-difficiles qui sont ni NP-complets ni indécidables. Par exemple, le langage des formule booléenne quantifiée est décidable dans l'espace polynomial, mais pas dans le temps polynomial non déterministe (à moins que NP = PSPACE)[3].
Références
- ↑ 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 )
- ↑ (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans 50 Years of Integer Programming 1958-2008, Springer Berlin Heidelberg, , 219–241 p. (ISBN 978-3-540-68274-5, DOI 10.1007/978-3-540-68279-0_8, lire en ligne)
- ↑ Plus précisément, ce langage est PSPACE-complet ; voir, par exemple, Ingo Wegener, Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, (ISBN 9783540210450, lire en ligne), p. 189.
