Problème P = NP

Par exemple, si vous avez un problème et que quelqu'un vous dit "La réponse à votre problème est l'ensemble des chiffres 1, 2, 3, 4, 5", un ordinateur peut être capable, rapidement, de déterminer si la réponse est bonne ou mauvaise, mais il peut mettre très longtemps à trouver "1, 2, 3, 4, 5" tout seul. Un autre exemple est la recherche de nombres premiers. Il est facile de vérifier si un nombre est premier, mais il est très difficile de trouver ces nombres en premier lieu. Pour certaines questions intéressantes et pratiques de ce type, nous n'avons aucun moyen de trouver rapidement une réponse, mais si on nous fournit une réponse, il est possible de vérifier - c'est-à-dire de vérifier - la réponse rapidement. De cette façon, les problèmes de PN peuvent être considérés comme des énigmes : il peut être difficile de trouver la réponse à une énigme, mais une fois que l'on entend la réponse, la réponse semble évidente. Dans cette comparaison (analogie), la question de base est la suivante : les énigmes sont-elles vraiment aussi difficiles que nous le pensons, ou est-ce qu'il nous manque quelque chose ?

Parce que ce genre de questions P contre NP est si important sur le plan pratique, de nombreux mathématiciens, scientifiques et programmeurs informatiques veulent prouver la proposition générale selon laquelle tout problème vérifié rapidement peut également être résolu rapidement. Cette question est suffisamment importante pour que le Clay Mathematical Institute accorde 1 000 000 de dollars à quiconque réussit à fournir une preuve ou une explication valable qui la réfute.

En creusant un peu plus, on constate que tous les problèmes P sont des problèmes NP : il est facile de vérifier qu'une solution est correcte en résolvant le problème et en comparant les deux solutions. Cependant, les gens veulent savoir le contraire : Existe-t-il des problèmes NP autres que des problèmes P, ou tous les problèmes NP sont-ils des problèmes P ? Si les problèmes NP ne sont vraiment pas les mêmes que les problèmes P (P ≠ NP), cela signifierait qu'il ne peut exister de moyens généraux et rapides de résoudre ces problèmes NP, peu importe les efforts que nous déployons. En revanche, si tous les problèmes NP sont des problèmes P (P = NP), cela signifierait qu'il existe de nouvelles méthodes très rapides de résolution des problèmes. Nous ne les avons tout simplement pas encore trouvées.

Comme les meilleurs efforts des scientifiques et des mathématiciens n'ont pas encore trouvé de méthodes générales et faciles pour résoudre les problèmes NP, beaucoup de gens pensent qu'il existe des problèmes NP autres que les problèmes P (c'est-à-dire que P ≠ NP est vrai). La plupart des mathématiciens pensent également que cela est vrai, mais actuellement, personne ne l'a prouvé par une analyse mathématique rigoureuse. S'il pouvait être prouvé que NP et P sont identiques (P = NP est vrai), cela aurait un impact énorme sur de nombreux aspects de la vie quotidienne. C'est pourquoi la question du P par rapport au NP est un sujet important et largement étudié.

Supposons que quelqu'un veuille construire deux tours, en empilant des roches de masse différente. On veut s'assurer que chacune des tours a exactement la même masse. Cela signifie que l'on devra mettre les roches en deux piles qui ont la même masse. Si l'on devine une division des roches qui pourrait fonctionner, il serait facile de vérifier si l'on a raison. (Pour vérifier la réponse, on peut diviser les roches en deux piles, puis utiliser une balance pour voir si elles ont la même masse). Parce qu'il est facile de vérifier ce problème, appelé "partition" par les informaticiens - plus facile que de le résoudre car, comme nous le verrons, ce n'est pas un problème P. ^[]

Est-il difficile à résoudre, carrément ? Si l'on commence avec seulement 100 roches, il y a 2^{100-1}-1 = 633,825,300,114,114,700,748,351,602,687, soit environ 6,3 x 10^{29} façons possibles (combinaisons) de diviser ces roches en deux piles. Si l'on pouvait vérifier chaque jour une combinaison unique de roches, cela prendrait 1,3 x 10^{22} ou 1 300 000 000 000 000 000 000 000 d'années d'effort. À titre de comparaison, les physiciens pensent que l'univers a environ 1,4 x 10^{10} ans (450 000 000 000 000 000 000 000 ou environ 4,5 x 10^{17} secondes, soit environ un trillionième du temps que prendrait notre effort d'empilement de roches. Cela signifie que si l'on prend tout le temps qui s'est écoulé depuis le début de l'univers, il faudrait vérifier plus de deux billions (2 000 000 000 000 000) de façons différentes de diviser les roches chaque seconde, afin de vérifier toutes les différentes façons.

Si l'on programmait un ordinateur puissant, pour tester toutes ces façons de diviser les roches, on pourrait vérifier 1 000 000 combinaisons par seconde en utilisant les systèmes actuels. Cela signifie qu'il faudrait encore 2 000 000 ordinateurs très puissants, fonctionnant depuis l'origine de l'univers, pour tester toutes les façons de diviser les roches.

Cependant, il peut être possible de trouver une méthode pour diviser les roches en deux piles égales sans vérifier toutes les combinaisons. La question "P est-il égal à NP ?" est un raccourci pour demander si une telle méthode peut exister.

Il existe de nombreux problèmes importants de PN que les gens ne savent pas comment résoudre d'une manière qui soit plus rapide que de tester toutes les réponses possibles. Voici quelques exemples :

• Un vendeur ambulant veut visiter 100 villes en voiture, en commençant et en terminant son voyage à la maison. Il dispose d'une réserve d'essence limitée, de sorte qu'il ne peut parcourir qu'un total de 10 000 kilomètres. Il veut savoir s'il peut visiter toutes les villes sans manquer d'essence.
• Une école propose 100 classes différentes, et un enseignant doit choisir une heure pour l'examen final de chaque classe. Pour éviter la tricherie, tous les élèves qui suivent un cours doivent passer l'examen de ce cours en même temps. Si un élève suit plus d'un cours, tous ces examens doivent avoir lieu à des heures différentes. L'enseignant veut savoir s'il peut programmer tous les examens le même jour afin que chaque élève puisse passer l'examen de chacune de ses classes.
• Un agriculteur veut apporter 100 pastèques de différentes masses au marché. Il doit emballer les pastèques dans des boîtes. Chaque boîte ne peut contenir que 20 kilos sans se casser. L'agriculteur doit savoir si 10 boîtes lui suffiront pour transporter les 100 pastèques au marché. (Ceci est trivial, si pas plus d'une pastèque pèse plus de 2 kg, on peut en placer 10 dans chacune des caisses, si pas plus de 10 pastèques pèsent plus de 2 kg, on peut en placer une dans chaque caisse, etc. pour une solution rapide ; l'observation sera la clé de toute solution rapide comme celle-ci ou le problème du nombre fixé).
• Une grande galerie d'art comporte de nombreuses pièces, et chaque mur est couvert de nombreuses peintures coûteuses. Le propriétaire de la galerie veut acheter des appareils photo pour regarder ces peintures, au cas où un voleur tenterait de les voler. Il veut savoir si 100 caméras lui suffiront pour s'assurer que chaque tableau peut être vu par au moins une caméra.
• Le problème de la clique : le directeur d'une école a une liste des élèves qui sont amis les uns avec les autres. Elle veut trouver un groupe de 10 % des élèves qui sont tous amis les uns avec les autres.

Dans l'exemple ci-dessus, nous voyons qu'avec 100 roches, il y a 2 100 façons de séparer l'ensemble des roches. Avec n roches, il y a 2 n combinaisons de style 2^{n}. La fonction f ( n ) = 2 n {\displaystyle f(n)=2^{n}} est une fonction exponentielle. Elle est importante pour NP car elle modélise le nombre de calculs nécessaires pour résoudre un problème dans le pire des cas et, par conséquent, le temps nécessaire dans le pire des cas.

Et jusqu'à présent, pour les problèmes difficiles, les solutions ont nécessité des calculs de l'ordre de 2 n {\displaystyle 2^{n}}. Pour chaque problème particulier, les gens ont trouvé des moyens de réduire le nombre de calculs nécessaires. On pourrait imaginer qu'une façon de ne faire qu'1% du nombre de calculs le plus défavorable et qui économise beaucoup de calculs, mais cela reste 0,01 × ( 2 n ) {\displaystyle 0,01\times (2^{n})} calculs. Et chaque pierre supplémentaire double encore le nombre de calculs nécessaires pour résoudre le problème. Certaines idées peuvent permettre de mettre au point des méthodes permettant de faire encore moins de calculs en produisant des variations du modèle : par exemple, 2 n / n 3 {\displaystyle 2^{n}/n^{3}} . Mais la fonction exponentielle domine toujours à mesure que le nombre d'écrans n augmente.

Considérez le problème de la programmation des examens (décrit ci-dessus). Mais supposons ensuite qu'il y ait 15 000 étudiants. Il y a un programme informatique qui prend les horaires de tous les 15000 étudiants. Il fonctionne en une heure et produit un calendrier d'examens afin que tous les étudiants puissent passer leurs examens en une semaine. Il satisfait à de nombreuses règles (pas d'examens consécutifs, pas plus de deux examens par période de 28 heures, ...) pour limiter le stress de la semaine d'examens. Le programme se déroule pendant une heure à la pause de mi-parcours et chacun connaît son emploi du temps pour les examens, ce qui lui laisse tout le temps de se préparer.

L'année suivante, cependant, il y a 10 étudiants de plus. Si le même programme tourne sur le même ordinateur, cette heure va se transformer en 2 10 heures, car chaque étudiant supplémentaire double les calculs. Cela fait 6 semaines ! S'il y avait 20 étudiants de plus, alors

2 20 {\displaystyle 2^{20}} heures = 1048576 {\displaystyle 1048576} heures ~ 43691 {\displaystyle 43691} jours ~ 113 {\displaystyle 113} années

Ainsi, pour 15 000 étudiants, cela prend une heure. Pour 15020 étudiants, cela prend 113 ans.

Comme vous pouvez le voir, les fonctions exponentielles se développent très rapidement. La plupart des mathématiciens pensent que les problèmes NP les plus difficiles nécessitent un temps exponentiel pour être résolus.

Les mathématiciens peuvent montrer qu'il existe des problèmes de NP qui sont NP-Complet. Un problème NP-Complet est au moins aussi difficile à résoudre que n'importe quel autre problème NP. Cela signifie que si quelqu'un trouvait une méthode pour résoudre rapidement un problème NP-Complet, il pourrait utiliser cette même méthode pour résoudre rapidement tous les problèmes NP. Tous les problèmes énumérés ci-dessus sont des problèmes NP-Complet, donc si le vendeur trouvait un moyen de planifier son voyage rapidement, il pourrait le dire à l'enseignante, et celle-ci pourrait utiliser cette même méthode pour programmer les examens. Le fermier pourrait utiliser la même méthode pour déterminer le nombre de boîtes dont il a besoin, et la femme pourrait utiliser la même méthode pour trouver un moyen de construire ses tours.

Parce qu'une méthode qui résout rapidement l'un de ces problèmes peut les résoudre tous, de nombreuses personnes veulent en trouver une. Cependant, comme il y a tant de problèmes différents de NP-Complet et que personne n'a encore trouvé le moyen de résoudre rapidement ne serait-ce qu'un seul d'entre eux, la plupart des experts pensent qu'il n'est pas possible de résoudre rapidement les problèmes de NP-Complet.

Propriétés de base

Dans la théorie de la complexité informatique, la classe de complexité NP-complete (abrégée NP-C ou NPC), est une classe de problèmes ayant deux propriétés :

• Il fait partie de l'ensemble des problèmes de NP (temps polynomial non déterministe) : Toute solution donnée au problème peut être vérifiée rapidement (en temps polynomial).
• Elle fait également partie de l'ensemble des problèmes difficiles des PN : Ceux qui sont au moins aussi difficiles que les problèmes les plus difficiles de la PN. Les problèmes qui sont difficiles pour le PN ne doivent pas nécessairement être des éléments du PN ; en fait, ils peuvent même ne pas être décidables.

Aperçu formel

NP-complet est un sous-ensemble de 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 résolus en temps polynomial sur une machine. Un problème p dans NP est également dans NPC si et seulement si tous les autres problèmes dans NP sont transformés en p en temps polynomial. NP-complet devait être utilisé comme un adjectif : les problèmes de la classe NP-complet étaient des problèmes NP+complet.

Les problèmes complets NP sont étudiés parce que la capacité de vérifier rapidement les solutions à un problème (NP) semble être en corrélation avec la capacité de résoudre rapidement le problème (P). On constate que chaque problème de NP est rapidement résolu, ce qu'on appelle le P = NP : ensemble de problèmes. Le problème unique dans NP-complet est résolu rapidement, plus rapidement que chaque problème dans NP également rapidement résolu, parce que la définition d'un problème NP-complet stipule que chaque problème dans NP doit pouvoir être rapidement réduit à chaque problème dans NP-complet (il est réduit en temps polynomial). [1]

Exemples

On sait que le problème de la satisfaction booléenne est NP complet. En 1972, Richard Karp a formulé 21 problèmes dont on sait qu'ils sont NP-complets. Ces problèmes sont connus sous le nom de 21 problèmes de Karp NP-complets. Ils comprennent des problèmes tels que le problème de programmation des entiers, qui applique des techniques de programmation linéaire aux entiers, le problème du sac à dos ou le problème du recouvrement des sommets.