NP-complétude et réductions

Un problème NP-complet est l'un des plus difficiles de la classe NP, en ce sens que tout problème NP s'y réduit efficacement, de sorte que la résolution rapide d'un seul problème NP-complet permettrait de résoudre tous les autres.

Definition

Un problème est NP-complet s'il appartient à la classe NP et si tout problème de la classe NP s'y réduit par une réduction en temps polynomial ; de tels problèmes sont les membres de NP les plus difficiles, équivalents les uns aux autres à une transformation efficace près.

Scope

Ce sujet couvre la classe NP des problèmes vérifiables en temps polynomial, les réductions plusieurs-à-un en temps polynomial, le théorème de Cook–Levin établissant la satisfiabilité comme NP-complète, le catalogue de Karp des problèmes combinatoires NP-complets, et la méthodologie de preuve de la NP-complétude de nouveaux problèmes par réduction à partir de problèmes connus.

Core questions

• Que signifie pour un problème d'être parmi les plus difficiles de la classe NP ?
• Comment le théorème de Cook–Levin identifie-t-il un premier problème NP-complet ?
• Comment les réductions sont-elles utilisées pour prouver qu'un nouveau problème est NP-complet ?
• Pourquoi la NP-complétude d'un problème a-t-elle des implications pour des milliers d'autres ?

Key theories

Cook–Levin theorem

La satisfiabilité booléenne est NP-complète car le calcul de tout vérificateur en temps polynomial peut être encodé comme une instance de satisfiabilité, fournissant le problème complet fondamental à partir duquel d'autres sont dérivés.

Les réductions de Karp et le réseau des problèmes NP-complets

Karp a montré que vingt-et-un problèmes naturels, de la coloration de graphes au problème de décision du voyageur de commerce, sont NP-complets par des réductions en temps polynomial, lançant la pratique d'établir la difficulté via un réseau croissant de réductions.

Clinical relevance

La NP-complétude est le diagnostic pratique de l'intractabilité : une fois qu'un problème d'ordonnancement, de logistique, de conception ou de vérification est démontré NP-complet, les ingénieurs cessent de rechercher un algorithme exact garanti rapide et se tournent vers des algorithmes d'approximation, des heuristiques, des solveurs de programmation en nombres entiers, ou des restrictions qui rendent le problème traitable.

History

Cook a prouvé la NP-complétude de la satisfiabilité en 1971, et Levin a obtenu indépendamment des résultats équivalents en Union soviétique. En 1972, Karp a démontré vingt-et-un problèmes NP-complets supplémentaires, révélant l'omniprésence du phénomène et faisant de la NP-complétude l'outil central pour diagnostiquer la difficulté computationnelle.

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp

Seminal works

• cook1971
• karp1972

Frequently asked questions

Que signifie NP ?

NP signifie temps polynomial non déterministe. De manière équivalente, un problème est dans NP si une solution proposée peut être vérifiée en temps polynomial, même si la trouver semble difficile. L'itinéraire du voyageur de commerce en dessous d'une longueur donnée est facile à vérifier une fois fourni, mais apparemment difficile à découvrir.

Comment prouve-t-on qu'un nouveau problème est NP-complet ?

Il faut démontrer deux choses : que le problème est dans NP, de sorte que les solutions candidates peuvent être vérifiées rapidement, et qu'un problème NP-complet connu s'y réduit en temps polynomial. La réduction transfère la difficulté connue, plaçant le nouveau problème parmi les plus difficiles de la classe NP.