Complétude NP

En théorie de la complexité computationnelle , un problème est NP-complet lorsque :

Il s'agit d'un problème de décision , ce qui signifie que pour toute entrée du problème, la sortie est soit « oui » soit « non ».
Lorsque la réponse est « oui », cela peut être démontré par l’existence d’une solution courte (de longueur polynomiale) .
L'exactitude de chaque solution peut être vérifiée rapidement (c'est-à-dire en temps polynomial ) et un algorithme de recherche par force brute peut trouver une solution en essayant toutes les solutions possibles.
Le problème peut être utilisé pour simuler tout autre problème pour lequel nous pouvons vérifier rapidement qu'une solution est correcte. En ce sens, les problèmes NP-complets sont les plus difficiles des problèmes pour lesquels les solutions peuvent être vérifiées rapidement. Si nous pouvions trouver rapidement des solutions à un problème NP-complet, nous pourrions rapidement trouver les solutions de tout autre problème pour lequel une solution donnée peut être facilement vérifiée.

Le nom « NP-complet » est l'abréviation de « nondeterministic polynomial-time complete ». Dans ce nom, « nondeterministic » fait référence aux machines de Turing non déterministes , une façon de formaliser mathématiquement l'idée d'un algorithme de recherche par force brute. Le temps polynomial fait référence à une quantité de temps considérée comme « rapide » pour qu'un algorithme déterministe vérifie une solution unique, ou pour qu'une machine de Turing non déterministe effectue la recherche complète. « Complet » fait référence à la propriété de pouvoir simuler tout ce qui se trouve dans la même classe de complexité .

Plus précisément, chaque entrée du problème doit être associée à un ensemble de solutions de longueur polynomiale, dont la validité de chacune peut être testée rapidement (en temps polynomial ), de telle sorte que la sortie pour toute entrée soit « oui » si l'ensemble de solutions n'est pas vide et « non » s'il est vide. La classe de complexité des problèmes de cette forme est appelée NP , une abréviation de « temps polynomial non déterministe ». Un problème est dit NP-difficile si tout ce qui est dans NP peut être transformé en temps polynomial en lui même s'il n'est pas dans NP. Un problème est NP-complet s'il est à la fois dans NP et NP-difficile. Les problèmes NP-complets représentent les problèmes les plus difficiles de NP. Si un problème NP-complet a un algorithme en temps polynomial, tous les problèmes de NP en ont. L'ensemble des problèmes NP-complets est souvent désigné par NP-C ou NPC .

Bien qu'une solution à un problème NP-complet puisse être vérifiée « rapidement », il n'existe aucun moyen connu de trouver une solution rapidement. Autrement dit, le temps nécessaire pour résoudre le problème à l'aide de n'importe quel algorithme connu augmente rapidement à mesure que la taille du problème augmente. Par conséquent, déterminer s'il est possible de résoudre ces problèmes rapidement, appelé le problème P versus NP , est l'un des problèmes fondamentaux non résolus de l'informatique aujourd'hui.

Bien qu'une méthode permettant de calculer rapidement les solutions aux problèmes NP-complets reste inconnue, les informaticiens et les programmeurs sont encore fréquemment confrontés à des problèmes NP-complets. Les problèmes NP-complets sont souvent traités à l'aide de méthodes heuristiques et d'algorithmes d'approximation .

Aperçu

Les problèmes NP-complets sont dans NP , l'ensemble de tous les problèmes de décision dont les solutions peuvent être vérifiées en temps polynomial ; NP peut être défini de manière équivalente comme l'ensemble des problèmes de décision qui peuvent être résolus en temps polynomial sur une machine de Turing non déterministe . Un problème p dans NP est NP-complet si tous les autres problèmes dans NP peuvent être transformés (ou réduits) en p en temps polynomial.

On ne sait pas si tous les problèmes de NP peuvent être résolus rapidement – c'est ce qu'on appelle le problème P versus NP . Mais si tout problème NP-complet peut être résolu rapidement, alors tous les problèmes de NP le peuvent, car la définition d'un problème NP-complet stipule que tout problème de NP doit être rapidement réductible à tout problème NP-complet (c'est-à-dire qu'il peut être réduit en temps polynomial). Pour cette raison, on dit souvent que les problèmes NP-complets sont plus difficiles ou plus difficiles que les problèmes NP en général.

Définition formelle

Un problème de décision est NP-complet si : ${\displaystyle \scriptstyle C <semantics> <mrow> <mstyle> <mstyle> <mi>C</mi> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle \scriptstyle C}</annotation> </semantics> </math><img src=$

${\displaystyle \scriptstyle C <semantics> <mrow> <mstyle> <mstyle> <mi>C</mi> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle \scriptstyle C}</annotation> </semantics> </math><img src=$
Tout problème en NP est réductible en temps polynomial. ${\displaystyle \scriptstyle C <semantics> <mrow> <mstyle> <mstyle> <mi>C</mi> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle \scriptstyle C}</annotation> </semantics> </math><img src=$

${\displaystyle \scriptstyle C <semantics> <mrow> <mstyle> <mstyle> <mi>C</mi> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle \scriptstyle C}</annotation> </semantics> </math><img src=$ ${\displaystyle \scriptstyle C <semantics> <mrow> <mstyle> <mstyle> <mi>C</mi> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle \scriptstyle C}</annotation> </semantics> </math><img src=$

Notez qu'un problème satisfaisant la condition 2 est dit NP-difficile , qu'il satisfasse ou non la condition 1.

Une conséquence de cette définition est que si nous avions un algorithme en temps polynomial (sur une UTM , ou toute autre machine abstraite équivalente à Turing ) pour , nous pourrions résoudre tous les problèmes de NP en temps polynomial. ${\displaystyle \scriptstyle C <semantics> <mrow> <mstyle> <mstyle> <mi>C</mi> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle \scriptstyle C}</annotation> </semantics> </math><img src=$

Arrière-plan

Le concept de NP-complétude a été introduit en 1971 (voir théorème de Cook-Levin ), bien que le terme NP-complet ait été introduit plus tard. Lors de la conférence STOC de 1971 , il y eut un débat acharné entre les informaticiens sur la question de savoir si les problèmes NP-complets pouvaient être résolus en temps polynomial sur une machine de Turing déterministe . John Hopcroft a amené tout le monde à la conférence à un consensus selon lequel la question de savoir si les problèmes NP-complets sont résolubles en temps polynomial devrait être reportée à une date ultérieure, car personne n'avait de preuve formelle de leurs affirmations dans un sens ou dans l'autre. C'est ce qu'on appelle « la question de savoir si P=NP ».

Personne n'a encore été en mesure de déterminer de manière concluante si les problèmes NP-complets sont en fait résolubles en temps polynomial, ce qui en fait l'un des grands problèmes non résolus des mathématiques . Le Clay Mathematics Institute offre une récompense d'un million de dollars ( Millennium Prize ) à quiconque aura une preuve formelle que P=NP ou que P≠NP.

L'existence de problèmes NP-complets n'est pas évidente. Le théorème de Cook-Levin stipule que le problème de satisfiabilité booléenne est NP-complet, établissant ainsi que de tels problèmes existent. En 1972, Richard Karp a prouvé que plusieurs autres problèmes étaient également NP-complets (voir les 21 problèmes NP-complets de Karp ) ; il existe donc une classe de problèmes NP-complets (en plus du problème de satisfiabilité booléenne). Depuis les résultats originaux, des milliers d'autres problèmes ont été démontrés comme étant NP-complets par des réductions d'autres problèmes précédemment démontrés comme étant NP-complets ; beaucoup de ces problèmes sont rassemblés dans Garey & Johnson (1979).

Problèmes NP-complets

La façon la plus simple de prouver qu'un nouveau problème est NP-complet est de prouver d'abord qu'il est NP, puis de réduire à ce niveau un problème NP-complet connu. Il est donc utile de connaître une variété de problèmes NP-complets. La liste ci-dessous contient quelques problèmes bien connus qui sont NP-complets lorsqu'ils sont exprimés sous forme de problèmes de décision.

À droite se trouve un diagramme de certains des problèmes et des réductions généralement utilisées pour prouver leur complétude NP. Dans ce diagramme, les problèmes sont réduits de bas en haut. Notez que ce diagramme est trompeur en tant que description de la relation mathématique entre ces problèmes, car il existe une réduction en temps polynomial entre deux problèmes NP-complets ; mais il indique où la démonstration de cette réduction en temps polynomial a été la plus facile.

Il n'y a souvent qu'une petite différence entre un problème dans P et un problème NP-complet. Par exemple, le problème de 3-satisfiabilité , une restriction du problème de satisfiabilité booléenne, reste NP-complet, alors que le problème de 2-satisfiabilité légèrement plus restreint est dans P (plus précisément, il est NL-complet ), mais le problème max. 2-sat. légèrement plus général est à nouveau NP-complet. Déterminer si un graphe peut être coloré avec 2 couleurs est dans P, mais avec 3 couleurs est NP-complet, même lorsqu'il est restreint aux graphes planaires . Déterminer si un graphe est un cycle ou est bipartite est très facile (dans L ), mais trouver un sous-graphe bipartite maximal ou un sous-graphe cyclique maximal est NP-complet. Une solution du problème du sac à dos dans un pourcentage fixe de la solution optimale peut être calculée en temps polynomial, mais trouver la solution optimale est NP-complet.

Problèmes intermédiaires

Un exemple intéressant est le problème de l'isomorphisme des graphes , le problème de la théorie des graphes qui consiste à déterminer si un isomorphisme de graphes existe entre deux graphes. Deux graphes sont isomorphes si l'un peut être transformé en l'autre simplement en renommant les sommets . Considérons ces deux problèmes :

Isomorphisme de graphe : Le graphe G ₁ est- il isomorphe au graphe G ₂ ?
Isomorphisme de sous-graphe : Le graphe G ₁ est- il isomorphe à un sous-graphe du graphe G ₂ ?

Le problème d'isomorphisme de sous-graphe est NP-complet. On suppose que le problème d'isomorphisme de graphes n'est ni dans P ni NP-complet, bien qu'il soit dans NP. Il s'agit d'un exemple de problème considéré comme difficile , mais qui n'est pas considéré comme NP-complet. Cette classe est appelée problèmes NP-intermédiaires et existe si et seulement si P≠NP.

Résolution de problèmes NP-complets

Actuellement, tous les algorithmes connus pour les problèmes NP-complets nécessitent un temps superpolynomial dans la taille d'entrée. Le problème de couverture de vertex a pour certains et on ne sait pas s'il existe des algorithmes plus rapides. ${\displaystyle O(1.2738^{k}+nk) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <msup> <mn>1.2738</mn> <mrow> <mi>k</mi> </mrow> </msup> <mo>+</mo> <mi>n</mi> <mi>k</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{ displaystyle O (1,2738 ^ {k} + nk)}</annotation> </semantics> </math><img src=$ $0 k > 0$ 0}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/27b3af208b148139eefc03f0f80fa94c38c5af45">

Les techniques suivantes peuvent être appliquées pour résoudre des problèmes de calcul en général, et elles donnent souvent lieu à des algorithmes sensiblement plus rapides :

Approximation : Au lieu de rechercher une solution optimale, recherchez une solution qui est au plus à un facteur d'une solution optimale.
Randomisation : utiliser le caractère aléatoire pour obtenir un temps d'exécution moyen plus rapide et permettre à l'algorithme d'échouer avec une faible probabilité. Remarque : la méthode de Monte-Carlo n'est pas un exemple d'algorithme efficace dans ce sens spécifique, bien que des approches évolutionnaires comme les algorithmes génétiques puissent l'être.
Restriction : En limitant la structure de l'entrée (par exemple, aux graphes planaires), des algorithmes plus rapides sont généralement possibles.
Paramétrage : Il existe souvent des algorithmes rapides si certains paramètres de l'entrée sont fixes.
Heuristique : Algorithme qui fonctionne « raisonnablement bien » dans de nombreux cas, mais pour lequel il n'existe aucune preuve qu'il soit à la fois toujours rapide et qu'il produise toujours un bon résultat. Des approches métaheuristiques sont souvent utilisées.

Un exemple d'algorithme heuristique est un algorithme de coloration gourmande sous-optimal utilisé pour la coloration des graphes pendant la phase d'allocation des registres de certains compilateurs, une technique appelée allocation globale de registres par coloration des graphes . Chaque sommet est une variable, les arêtes sont dessinées entre les variables qui sont utilisées en même temps et les couleurs indiquent le registre attribué à chaque variable. Étant donné que la plupart des machines RISC disposent d'un nombre assez important de registres à usage général, même une approche heuristique est efficace pour cette application. ${\displaystyle O(n\log n) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <mi>n</mi> <mi>enregistrer</mi> <mo>⁡</mo> <mi>n</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle O(n\log n)}</annotation> </semantics> </math><img src=$

Complétude sous différents types de réduction

Dans la définition de NP-complet donnée ci-dessus, le terme réduction a été utilisé dans le sens technique d'une réduction plusieurs-un en temps polynomial .

Un autre type de réduction est la réduction de Turing en temps polynomial . Un problème est réductible en temps polynomial à un problème si, étant donné une sous-routine qui se résout en temps polynomial, on peut écrire un programme qui appelle cette sous-routine et se résout en temps polynomial. Cela contraste avec la réductibilité plusieurs-uns, qui a la restriction que le programme ne peut appeler la sous-routine qu'une seule fois, et la valeur de retour de la sous-routine doit être la valeur de retour du programme. ${\displaystyle \scriptstyle X <semantics> <mrow> <mstyle> <mstyle> <mi>X</mi> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle \scriptstyle X}</annotation> </semantics> </math><img src=$ ${\displaystyle \scriptstyle Y <semantics> <mrow> <mstyle> <mstyle> <mi>Y</mi> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle \scriptstyle Y}</annotation> </semantics> </math><img src=$ ${\displaystyle \scriptstyle Y <semantics> <mrow> <mstyle> <mstyle> <mi>Y</mi> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle \scriptstyle Y}</annotation> </semantics> </math><img src=$ ${\displaystyle \scriptstyle X <semantics> <mrow> <mstyle> <mstyle> <mi>X</mi> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle \scriptstyle X}</annotation> </semantics> </math><img src=$

Si l'on définit l'analogue du NP-complet avec des réductions de Turing au lieu de réductions plusieurs-un, l'ensemble de problèmes résultant ne sera pas plus petit que le NP-complet ; la question de savoir s'il sera plus grand reste ouverte.

Un autre type de réduction qui est également souvent utilisé pour définir la NP-complétude est la réduction plusieurs-un dans l'espace logarithmique , qui est une réduction plusieurs-un qui peut être calculée avec seulement une quantité logarithmique d'espace. Étant donné que chaque calcul qui peut être effectué dans l'espace logarithmique peut également être effectué en temps polynomial, il s'ensuit que s'il existe une réduction plusieurs-un dans l'espace logarithmique, il existe également une réduction plusieurs-un en temps polynomial. Ce type de réduction est plus raffiné que les réductions plusieurs-un en temps polynomial plus courantes et il nous permet de distinguer plus de classes telles que P-complètes . La question de savoir si sous ces types de réduction la définition de NP-complète change reste un problème ouvert. Tous les problèmes NP-complets actuellement connus sont NP-complets sous des réductions d'espace logarithmique. Tous les problèmes NP-complets actuellement connus restent NP-complets même sous des réductions beaucoup plus faibles telles que les réductions et les réductions. Certains problèmes NP-complets tels que SAT sont connus pour être complets même sous des projections en temps polylogarithmique. On sait cependant que les réductions AC ⁰ définissent une classe strictement plus petite que les réductions en temps polynomial. ${\displaystyle AC_{0 <semantics> <mrow> <mstyle> <mi>UN</mi> <msub> <mi>C</mi> <mrow> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle AC_{0}}</annotation> </semantics> </math><img src=$ ${\displaystyle NC_{0 <semantics> <mrow> <mstyle> <mi>N</mi> <msub> <mi>C</mi> <mrow> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle NC_{0}}</annotation> </semantics> </math><img src=$

Appellation

Selon Donald Knuth , le nom « NP-complet » a été popularisé par Alfred Aho , John Hopcroft et Jeffrey Ullman dans leur célèbre manuel « The Design and Analysis of Computer Algorithms ». Il rapporte qu'ils ont introduit le changement dans les preuves en galère pour le livre (de « polynomialement complet »), conformément aux résultats d'un sondage qu'il avait mené auprès de la communauté de l'informatique théorique . D'autres suggestions faites dans le sondage comprenaient « herculéen », « formidable », « dur à cuire » de Steiglitz en l'honneur de Cook, et l'acronyme de Shen Lin « PET », qui signifiait « temps probablement exponentiel », mais selon la direction du problème P versus NP , pourrait signifier « temps prouvablement exponentiel » ou « temps précédemment exponentiel ».

Idées fausses courantes

Les idées fausses suivantes sont fréquentes.

« Les problèmes NP-complets sont les problèmes connus les plus difficiles. » Comme les problèmes NP-complets sont de type NP, leur temps d'exécution est au plus exponentiel. Cependant, il a été prouvé que certains problèmes nécessitent plus de temps, par exemple l'arithmétique de Presburger . Il a même été prouvé que certains problèmes ne peuvent jamais être résolus du tout, par exemple le problème de l'arrêt .
« Les problèmes NP-complets sont difficiles car il existe de nombreuses solutions différentes. » D'un côté, il existe de nombreux problèmes qui ont un espace de solutions tout aussi grand, mais qui peuvent être résolus en temps polynomial (par exemple l'arbre couvrant minimal ). D'un autre côté, il existe des problèmes NP avec au plus une solution qui sont NP-difficiles sous réduction polynomiale randomisée (voir le théorème de Valiant–Vazirani ).
« La résolution de problèmes NP-complets nécessite un temps exponentiel. » Tout d'abord, cela impliquerait que P ≠ NP, ce qui est toujours une question non résolue. De plus, certains problèmes NP-complets ont en fait des algorithmes exécutés en temps superpolynomial, mais sous-exponentiel comme O(2 ^{√ n} n ). Par exemple, les problèmes d'ensemble indépendant et d'ensemble dominant pour les graphes planaires sont NP-complets, mais peuvent être résolus en temps sous-exponentiel en utilisant le théorème du séparateur planaire .
« Chaque instance d'un problème NP-complet est difficile. » Souvent, certaines instances, ou même la plupart des instances, peuvent être faciles à résoudre en temps polynomial. Cependant, à moins que P=NP, tout algorithme en temps polynomial doit asymptotiquement être faux sur plus d'un nombre polynomial d'entrées exponentiellement nombreuses d'une certaine taille.
« Si P=NP, tous les chiffrements cryptographiques peuvent être déchiffrés. » Un problème en temps polynomial peut être très difficile à résoudre en pratique si le degré ou les constantes du polynôme sont suffisamment grands. De plus, la sécurité basée sur la théorie de l'information fournit des méthodes cryptographiques qui ne peuvent pas être déchiffrées, même avec une puissance de calcul illimitée.
« Un ordinateur quantique à grande échelle serait capable de résoudre efficacement les problèmes NP-complets. » La classe de problèmes de décision qui peuvent être résolus efficacement (en principe) par un ordinateur quantique tolérant aux pannes est connue sous le nom de BQP. Cependant, on ne pense pas que BQP contienne tous les problèmes NP, et si ce n'est pas le cas, alors il ne peut contenir aucun problème NP-complet.

Propriétés

En considérant un problème de décision comme un langage formel dans un codage fixe, l'ensemble NPC de tous les problèmes NP-complets n'est pas fermé sous :

On ne sait pas si NPC est fermé sous complémentation , puisque NPC= co-NPC si et seulement si NP= co-NP , et puisque NP=co-NP est une question ouverte .