Voici, traduite en français, la définition de la conjecture « P vs NP » telle qu’on la trouve sur Wikipédia en anglais. Partons de la version en anglais car la définition de l’entrée en français est d’emblée assez alambiquée :
« Le problème P vs NP est un problème majeur non résolu en informatique. Il s’agit de savoir si tout problème dont la solution peut être vérifiée rapidement peut également être résolu rapidement. »
Examinons quelques exemples de problèmes dans cette perspective d’une comparaison entre vitesse de résolution et vitesse de confirmation que le problème a bien été résolu.
Premier cas : ce genre de casse-tête où l’on vous propose deux pièces de métal imbriquées en vous mettant au défi de les séparer.
Si vous êtes paresseux, ou avez jeté l’éponge au bout d’un moment, vous trouverez la solution sur le mode d’emploi qui accompagne le jeu. Comme il vous est montré, celle-ci consiste en une ou plusieurs rotations des pièces l’une par rapport à l’autre suivie d’un alignement très particulier permettant de les désemboîter.
Ce sont de petits dessins qui vous permettent de saisir aisément les manipulations ad hoc. S’il fallait cependant décrire entièrement l’opération sans recourir à une aide visuelle, une telle description exigerait dans la plupart des cas, un nombre considérable de phrases.
Par contre, vérifier que le problème a bien été résolu ne requiert qu’un examen visuel d’une fraction de seconde : il suffit de constater que les deux pièces ont effectivement été séparées.
Second cas : celui d’un puzzle.
Décrire une procédure de solution pourrait débuter de la manière suivante :
« Mettre à part les pièces ayant un bord plat.
Parmi les pièces ayant un bord plat, les séparer en deux groupes : les pièces à tenons et les pièces à mortaises.
Prendre une pièce d’un des deux groupes et chercher grâce à la similarité de couleur une pièce de l’autre groupe à laquelle elle pourrait s’emboîter.
Répéter jusqu’à épuisement des pièces à bord plat. Se tourner ensuite vers les autres pièces.
Etc. »
Vérifier que le problème est bien résolu ne requiert dans ce cas aussi qu’un examen visuel d’une fraction de seconde : il suffit d’observer qu’il n’existe pas de trou dans l’image reproduisant celle du couvercle de la boîte du puzzle dont on se demande s’il est effectivement terminé. Tout cela est extrêmement banal : vérifier que le problème posé a bien été résolu est quasi instantané, et sans commune mesure avec la difficulté à le faire.
Donc si « La conjecture P vs NP consiste à savoir si tout problème dont la solution peut être vérifiée rapidement peut également être résolu rapidement », les deux exemples du casse-tête et du puzzle montrent clairement qu’il existe des problèmes dont la solution peut être vérifiée rapidement sans qu’ils puissent être résolus rapidement.
Mieux, les deux exemples choisis suggèrent fortement qu’il n’existe aucun lien entre la difficulté du problème et celle de la vérification qu’il a bien été résolu.
Ce qui ne peut signifier qu’une seule chose : que la définition de P vs NP dont nous sommes partis n’est pas la bonne, la réponse étant trop évidente si on la prenait à la lettre, et n’aurait certainement pas mobilisé une génération de mathématiciens. Il faut donc aborder et examiner P vs NP autrement.
La définition de P vs NP du Clay Mathematical Institute
Abordons les choses autrement : partons du texte du Clay Mathematical Institute qui offre un prix d’un million de dollars pour la solution de la conjecture P vs NP. Elle y est caractérisée de manière intuitive, à entendre par opposition à de manière formelle, c’est-à-dire « avec des équations ».
Sur le site du Clay Mathematical Institute : « Imaginons que vous deviez organiser le logement d’un groupe de quatre cents étudiants. Les places sont limitées et seuls cent étudiants pourront être accueillis au foyer. Pour compliquer les choses, le doyen vous a fourni une liste de paires d’étudiants jugés incompatibles et a demandé qu’aucune paire de cette liste ne figure dans votre choix final.
Il s’agit d’un exemple de ce que les informaticiens appellent un problème NP, puisqu’il est facile de vérifier si un choix donné de cent étudiants proposé par un collègue satisfait aux critères (à savoir qu’aucune paire présente dans la liste de votre collègue n’apparaisse également dans la liste du bureau du doyen), mais la tâche consistant à générer une telle liste à partir de rien (from scratch) semble si difficile qu’elle est totalement irréalisable. En effet, le nombre total de façons de choisir cent étudiants parmi les quatre cents candidats est supérieur au nombre d’atomes dans l’univers connu ! Ainsi, aucune civilisation future ne pourra jamais espérer construire un superordinateur capable de résoudre le problème par la force brute, c’est-à-dire en vérifiant toutes les combinaisons possibles de 100 étudiants.
Toutefois, cette difficulté apparente ne reflète peut-être que le manque d’ingéniosité de votre programmeur. En fait, l’un des problèmes majeurs de l’informatique est de déterminer s’il existe des questions dont la réponse peut être rapidement vérifiée, mais dont la résolution par une procédure directe est extrêmement longue. Des problèmes tels que celui invoqué ci-dessus semblent certainement être de ce type, mais jusqu’à présent, personne n’a réussi à prouver que l’un d’entre eux est vraiment aussi difficile qu’il n’y paraît, c’est-à-dire qu’il n’existe pas de moyen réalisable de générer une réponse à l’aide d’un ordinateur. Stephen Cook et Leonid Levin ont formulé indépendamment en 1971 le problème P (c’est-à-dire facile à trouver) versus NP (c’est-à-dire facile à vérifier). »
Reprenons la question à partir de cette caractérisation du problème, « P » signifiant facile à résoudre vs « NP » voulant dire facile à vérifier, dans le cas particulier présenté : comment organiser l’hébergement de 400 étudiants dont seuls 100 en réalité peuvent être accueillis, assorti d’une contrainte : ne pas mettre dans la même chambre deux personnes incompatibles dont la liste a été établie par ailleurs. Il nous est dit qu’il y a là un exemple typique de problème non-P.
Quand Stephen Wolfram observe dans son A Project to Find the Fundamental Theory of Physics, qu’« il n’y a pas de méthode générale de raccourcir la série d’étapes nécessaires pour dériver un théorème. En d’autres termes, il peut être arbitrairement difficile d’obtenir un résultat en mathématiques » (2020 : 558-59), il s’agit d’une considération du même type : la carte d’un désert peut être extrêmement petite par rapport à la surface du désert lui-même, alors que pour un paysage très accidenté, il n’est pas possible de dresser une carte fidèle beaucoup plus petite que le pays lui-même. Tout dépend du cas. Tout est là ! C’est de cela également qu’il s’agit, on le devine, avec P vs NP, d’une réticence, toute mathématicienne, à admettre que « tout dépende du cas », une caractéristique propre au monde qui nous entoure, mais heureusement absente en général du monde des mathématiciens.
Et, si c’est de cela qu’il s’agit, pourquoi les mathématiciens et les informaticiens ont-ils même voulu formuler cette conjecture P vs NP, de la relation entre problème P, facile à résoudre, et problème NP, c’est-à-dire facile à vérifier ? Uniquement sans doute parce que le problème que l’on choisit comme cas typique de P vs NP (cf. ci-dessus : le logement d’un certain nombre de personnes en excédent du nombre de logements disponibles, alors qu’existent des incompatibilités entre ces personnes) suggère une similarité entre la solution (un certain nombre d’opérations à faire) et la vérification (un certain nombre d’autres opérations à faire), alors que d’autres exemples de problèmes, comme ceux du casse-tête et du puzzle, ne suggèrent pas, voire excluent, qu’il existerait une quelconque similarité entre procédure de solution du problème et procédure de vérification qu’il a effectivement été résolu.
(à suivre…)
Laisser un commentaire