P=NP, problème fondamental du calcul mathématique

Le problème P = NP est le problème fondamental du calcul mathématique. À partir de quel moment, et sous quelles conditions, un énoncé difficile à démontrer et jugé très probable doit-il être adopté comme nouvel axiome ?

Il n’y a qu’à, entend-on dire : avec les ordinateurs, on peut tout calculer ! Pour trouver le chemin de longueur minimale reliant un certain nombre de villes, il n’y a qu’à envisager tous les chemins et prendre le plus court. Pour déterminer si un nombre est premier, il suffit d’essayer de le diviser par tous les nombres plus petits que lui et voir si les restes sont nuls... Pour savoir si la position de celui qui commence aux échecs est gagnante, il n’y a qu’à examiner toutes les parties possibles. Hélas, ces calculs simples au premier abord sont beaucoup trop longs, même pour le plus puissant des ordinateurs. Peut-on les contourner ? C'est la question que pose l'énigme principale de l’informatique théorique « P = NP ? »

La question « P = NP ? » est l'un de sept problèmes sélectionnés par l'Institut Clay en l'an 2000 : comme pour les six autres, une somme d'un million de dollars attend celle, celui ou ceux qui le résoudront. Certains affirment que c'est le plus important des sept problèmes et donc la principale énigme des mathématiques d’aujourd'hui. Il semble aussi être le seul dont la résolution aurait des conséquences pratiques (il est lié à des centaines d’énoncés concrets) et sa portée philosophique est la plus grande : la question « P = NP ? » concerne la nature de la recherche de solution(s) dans un ensemble exponentiel de possibilités, ce qui est le problème même de la recherche scientifique. La question « P = NP ? » signifie à peu près : « Ce que nous pouvons trouver rapidement lorsque nous avons de la chance, peut-il être trouvé aussi vite par un calcul intelligent ? ». Très sommairement, « l'intelligence peut-elle remplacer la chance ? »

Une autre formulation est : « Tout ce que l'on peut vérifier facilement, peut-il être découvert aisément ? ». Vérifier qu’un chemin dans un graphe passe par tous les nœuds du graphe sans jamais passer deux fois par le même nœud (chemin hamiltonien) est facile, trouver le chemin n’est pas facile (aujourd'hui, aucun algorithme efficace ne le permet). En revanche, si P = NP, savoir s'il existe des chemins hamiltoniens sera facile.

On entend souvent que le problème « P = NP ? » est, parmi les sept problèmes récompensés par l'Institut Clay, celui le plus susceptible d'être résolu par un amateur. C'est exact dans le sens où son énoncé est plus simple à comprendre que celui des autres problèmes et qu'il est envisageable qu'une solution élémentaire soit proposée demain par un génial passionné. La situation était la même pour le grand théorème de Fermat ; cela ne signifie cependant pas que la solution était facile et, pour Fermat, c'est un professionnel qui a résolu l'énigme. Nous avons aujourd'hui de fortes raisons de craindre que la question « P = NP ? » soit d'une profonde et extrême difficulté.

Lire la suite de ce très intéressant article de Jean-Paul Delahaye sur le site Interstices.