Voici, traduite en fran\u00e7ais, la d\u00e9finition de la conjecture \u00ab\u00a0P vs NP\u00a0\u00bb telle qu\u2019on la trouve sur Wikip\u00e9dia en anglais<\/a>. Partons de la version en anglais car la d\u00e9finition de l\u2019entr\u00e9e en fran\u00e7ais est d\u2019embl\u00e9e assez alambiqu\u00e9e :<\/p>\n \u00ab Le probl\u00e8me P vs NP est un probl\u00e8me majeur non r\u00e9solu en informatique. Il s’agit de savoir si tout probl\u00e8me dont la solution peut \u00eatre v\u00e9rifi\u00e9e rapidement peut \u00e9galement \u00eatre r\u00e9solu rapidement. \u00bb<\/i><\/p>\n Examinons quelques exemples de probl\u00e8mes dans cette perspective d\u2019une comparaison entre vitesse de r\u00e9solution et vitesse de confirmation que le probl\u00e8me a bien \u00e9t\u00e9 r\u00e9solu.<\/p>\n Premier cas : ce genre de casse-t\u00eate o\u00f9 l\u2019on vous propose deux pi\u00e8ces de m\u00e9tal imbriqu\u00e9es en vous mettant au d\u00e9fi de les s\u00e9parer.<\/p>\n Si vous \u00eates paresseux, ou avez jet\u00e9 l\u2019\u00e9ponge au bout d\u2019un moment, vous trouverez la solution sur le mode d\u2019emploi qui accompagne le jeu. Comme il vous est montr\u00e9, celle-ci consiste en une ou plusieurs rotations des pi\u00e8ces l\u2019une par rapport \u00e0 l\u2019autre suivie d\u2019un alignement tr\u00e8s particulier permettant de les d\u00e9sembo\u00eeter.<\/p>\n Ce sont de petits dessins qui vous permettent de saisir ais\u00e9ment les manipulations ad hoc. S\u2019il fallait cependant d\u00e9crire enti\u00e8rement l\u2019op\u00e9ration sans recourir \u00e0 une aide visuelle, une telle description exigerait dans la plupart des cas, un nombre consid\u00e9rable de phrases.<\/p>\n Par contre, v\u00e9rifier que le probl\u00e8me a bien \u00e9t\u00e9 r\u00e9solu ne requiert qu\u2019un examen visuel d\u2019une fraction de seconde : il suffit de constater que les deux pi\u00e8ces ont effectivement \u00e9t\u00e9 s\u00e9par\u00e9es.<\/p>\n Second cas : celui d\u2019un puzzle.<\/p>\n D\u00e9crire une proc\u00e9dure de solution pourrait d\u00e9buter de la mani\u00e8re suivante :<\/p>\n \u00ab\u00a0Mettre \u00e0 part les pi\u00e8ces ayant un bord plat.<\/p>\n Parmi les pi\u00e8ces ayant un bord plat, les s\u00e9parer en deux groupes : les pi\u00e8ces \u00e0 tenons et les pi\u00e8ces \u00e0 mortaises.<\/p>\n Prendre une pi\u00e8ce d\u2019un des deux groupes et chercher gr\u00e2ce \u00e0 la similarit\u00e9 de couleur une pi\u00e8ce de l\u2019autre groupe \u00e0 laquelle elle pourrait s\u2019embo\u00eeter.<\/p>\n R\u00e9p\u00e9ter jusqu\u2019\u00e0 \u00e9puisement des pi\u00e8ces \u00e0 bord plat. Se tourner ensuite vers les autres pi\u00e8ces.<\/p>\n Etc.\u00a0\u00bb<\/p>\n V\u00e9rifier que le probl\u00e8me est bien r\u00e9solu ne requiert dans ce cas aussi qu\u2019un examen visuel d\u2019une fraction de seconde : il suffit d\u2019observer qu\u2019il n\u2019existe pas de trou dans l\u2019image reproduisant celle du couvercle de la bo\u00eete du puzzle dont on se demande s\u2019il est effectivement termin\u00e9. Tout cela est extr\u00eamement banal : v\u00e9rifier que le probl\u00e8me pos\u00e9 a bien \u00e9t\u00e9 r\u00e9solu est quasi instantan\u00e9, et sans commune mesure avec la difficult\u00e9 \u00e0 le faire.<\/p>\n Donc si \u00ab La conjecture P vs NP consiste \u00e0 savoir si tout probl\u00e8me dont la solution peut \u00eatre v\u00e9rifi\u00e9e rapidement peut \u00e9galement \u00eatre r\u00e9solu rapidement \u00bb, les deux exemples du casse-t\u00eate et du puzzle montrent clairement qu\u2019il existe des probl\u00e8mes dont la solution peut \u00eatre v\u00e9rifi\u00e9e rapidement sans qu\u2019ils puissent \u00eatre r\u00e9solus rapidement.<\/p>\n Mieux, les deux exemples choisis sugg\u00e8rent fortement qu\u2019il n\u2019existe aucun lien entre la difficult\u00e9 du probl\u00e8me et celle de la v\u00e9rification qu\u2019il a bien \u00e9t\u00e9 r\u00e9solu.<\/p>\n Ce qui ne peut signifier qu\u2019une seule chose : que la d\u00e9finition de P vs NP dont nous sommes partis n\u2019est pas la bonne, la r\u00e9ponse \u00e9tant trop \u00e9vidente si on la prenait \u00e0 la lettre, et n\u2019aurait certainement pas mobilis\u00e9 une g\u00e9n\u00e9ration de math\u00e9maticiens. Il faut donc aborder et examiner P vs NP autrement.<\/p>\n La d\u00e9finition de P vs NP du Clay Mathematical Institute<\/i><\/p>\n Abordons les choses autrement : partons du texte du Clay Mathematical Institute<\/i> qui offre un prix d\u2019un million de dollars pour la solution de la conjecture P vs NP. Elle y est caract\u00e9ris\u00e9e de mani\u00e8re intuitive, \u00e0 entendre par opposition \u00e0 de mani\u00e8re formelle, c\u2019est-\u00e0-dire \u00ab avec des \u00e9quations \u00bb.<\/p>\n