Quelle est la différence entre NP-difficile et NP-complet ?

Un problème est NP-difficile si tout problème de NP se réduit à lui en temps polynomial, mais il n'a pas nécessairement besoin d'être lui-même dans NP et n'a pas nécessairement besoin d'être un problème de décision. Un problème est NP-complet s'il est à la fois NP-difficile et dans NP. Les problèmes NP-complets sont les problèmes les plus difficiles qui restent dans NP.

La NP-complétude signifie-t-elle qu'un problème ne peut jamais être résolu ?

Non. Cela signifie qu'aucun algorithme en temps polynomial n'est connu pour toutes les entrées et qu'il est probable qu'il n'en existe pas si P n'est pas égal à NP. En pratique, de tels problèmes sont abordés avec des algorithmes d'approximation, des heuristiques, des solveurs en temps exponentiel qui fonctionnent sur des instances réalistes, ou en se restreignant à des cas particuliers.

Complétude NP et Intraitabilité

La complétude NP identifie les problèmes les plus difficiles de la classe NP — ceux auxquels tout problème NP se réduit — et fournit le cadre standard pour reconnaître les problèmes pour lesquels aucun algorithme efficace n'est connu ou probable.

Trouver un sujet avec PaperMindBientôtFind papers & topics

Tools & resources

Télécharger les diapositives

Learn & explore

VidéoBientôt

Definition

Un problème de décision est NP-complet s'il appartient à NP (ses instances positives possèdent des certificats vérifiables efficacement) et si tout problème de NP se réduit à lui en temps polynomial ; de tels problèmes sont les plus difficiles de NP, et un algorithme en temps polynomial pour l'un d'entre eux en produirait un pour tous.

Scope

Ce sujet couvre les classes de complexité P et NP, les réductions polynomiales, les définitions de la NP-difficulté (NP-hardness) et de la NP-complétude (NP-completeness), le théorème de Cook-Levin établissant la satisfiabilité comme NP-complète, le catalogue de problèmes NP-complets de Karp, et les conséquences pratiques de l'intraitabilité pour la conception d'algorithmes. Il applique ces concepts à la reconnaissance et à la gestion des problèmes difficiles ; la théorie formelle plus large des classes de complexité computationnelle est traitée dans le sous-domaine de la théorie de la calculabilité.

Core questions

Qu'est-ce qui distingue les classes de complexité P et NP ?
Comment une réduction en temps polynomial transfère-t-elle la difficulté d'un problème à un autre ?
Qu'établit le théorème de Cook-Levin, et pourquoi la satisfiabilité est-elle centrale ?
Comment un nouveau problème est-il prouvé NP-complet par réduction à partir d'un problème connu ?
Une fois qu'un problème est démontré NP-difficile, quelles stratégies algorithmiques subsistent ?

Key concepts

classe de complexité P
classe de complexité NP
réduction en temps polynomial
NP-difficulté
NP-complétude
théorème de Cook-Levin
problème de satisfiabilité booléenne (SAT)
problème P versus NP

Key theories

Théorème de Cook-Levin: Le théorème de Cook-Levin prouve que le problème de satisfiabilité booléenne (SAT) est NP-complet : tout problème de NP se réduit à lui en temps polynomial, fournissant le premier problème NP-complet et le point d'ancrage pour prouver la difficulté d'autres problèmes.
Réductibilité entre problèmes combinatoires: Karp a montré que les réductions en temps polynomial relient de nombreux problèmes naturels — clique, couverture de sommets, cycle hamiltonien, partition et autres — en un réseau de problèmes NP-complets, de sorte que chacun peut être prouvé difficile par réduction à partir d'un autre.

Clinical relevance

Reconnaître qu'un problème est NP-complet est l'un des résultats les plus utiles en pratique en informatique : cela indique aux ingénieurs de ne pas s'attendre à un algorithme exact rapide et de déployer plutôt des algorithmes d'approximation, des heuristiques, des solveurs exacts optimisés pour des instances typiques, ou des restrictions à des cas particuliers traitables. De nombreux problèmes d'ordonnancement, de routage, d'empaquetage et de conception sont NP-complets.

History

Stephen Cook a introduit la NP-complétude en 1971, prouvant que SAT est NP-complet ; Leonid Levin a obtenu des résultats similaires indépendamment. L'article de Richard Karp de 1972 a montré que 21 problèmes naturels sont NP-complets, établissant la portée du cadre. Le livre de Garey et Johnson de 1979 a catalogué des centaines de problèmes NP-complets et est devenu la référence standard.

Debates

P versus NP: Savoir si P est égal à NP — c'est-à-dire si tout problème vérifiable efficacement est également résoluble efficacement — est le problème ouvert le plus important du domaine ; presque tous les chercheurs conjecturent que P n'est pas égal à NP, mais la question reste non résolue et constitue l'un des problèmes du prix du millénaire.

Key figures

Stephen Cook
Richard Karp
Leonid Levin
Michael Garey
David Johnson

Seminal works

cook1971
karp1972
cormen2009

Frequently asked questions

Quelle est la différence entre NP-difficile et NP-complet ?: Un problème est NP-difficile si tout problème de NP se réduit à lui en temps polynomial, mais il n'a pas nécessairement besoin d'être lui-même dans NP et n'a pas nécessairement besoin d'être un problème de décision. Un problème est NP-complet s'il est à la fois NP-difficile et dans NP. Les problèmes NP-complets sont les problèmes les plus difficiles qui restent dans NP.
La NP-complétude signifie-t-elle qu'un problème ne peut jamais être résolu ?: Non. Cela signifie qu'aucun algorithme en temps polynomial n'est connu pour toutes les entrées et qu'il est probable qu'il n'en existe pas si P n'est pas égal à NP. En pratique, de tels problèmes sont abordés avec des algorithmes d'approximation, des heuristiques, des solveurs en temps exponentiel qui fonctionnent sur des instances réalistes, ou en se restreignant à des cas particuliers.