NP-difficile

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.

Mise en évidence d'un problème NP-difficile si Problème P ≟ 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].