L’intelligence peut-elle remplacer la chance ? 

Tribune | Mohamed Ali Mahjoub – Ecole Nationale d’Ingénieurs de Sousse

Avoir à sa disposition une grande puissance de calcul suffirait-il pour obtenir de l’intelligence ? Probablement non, ça serait bien trop simple. Étant donné un sac de capacité 15 kg, et N objets possédant chacun un poids et une valeur (Fig. 1), pour savoir quels objets faut-il mettre dans le sac de manière à maximiser la valeur totale sans dépasser le poids maximal, on n’a qu’à envisager toutes les combinaisons possibles et en retenir la meilleur.

Hélas, ce calcul si simple à première impression est beaucoup trop long dans les cas pratiques, même pour le plus puissant des ordinateurs. Pour des grandes valeurs de N le temps mis est bien très long car il croît en exponentielle comme 2N ! (*) Par contre, si l’on se donne un échantillon de l’ensemble d’objets, il est facile de vérifier si la contrainte énoncée en haut est satisfaite ou non. Cette difficulté apparente reflète-elle un manque d’ingéniosité ?

Peut-on trouver rapidement ces objets grâce à un programme informatique intelligent ? Ainsi l’on se demande si une solution facile à vérifier, est facile à trouver ? C’est la question que pose l’énigme principale de l’informatique théorique P=NP ? Il s’agit d‘une conjecture émise depuis 1971 par Stephen Cook, professeur à l’université de Toronto. Aujourd’hui encore, aucune certitude à propos de cette assertion !

1- De la difficulté à la complexité

Expliquons les choses de manière simple. Certains problèmes sont plus difficiles que d’autres. Par exemple, étant donné un nombre, par simple intuition on peut tester si ce nombre est divisible par 10 ou non : il suffit de voir si le dernier chiffre est égal à zéro. Cependant, il est beaucoup plus difficile de déterminer sa décomposition en produits de facteurs premiers.

Pour étudier scientifiquement la difficulté intrinsèque de problèmes, on fait appel à la théorie de complexité qui permet d’organiser les problèmes par classes de complexité ayant des propriétés communes. Elle étudie aussi les limites de calcul pour résoudre un problème donné. On distingue deux grandes classes de complexité ; la classe des problèmes, de complexité P, faciles à résoudre et la classe des problèmes, de complexité NP dont les solutions sont faciles à vérifier.

Il est clair qu’un problème facile à résoudre a des solutions faciles à vérifier (x-5 = 3 : la solution est facile à trouver, x= 5+3= 8, et facile à vérifier 8-5=3). Ceci veut dire que l’ensemble P est inclus dans l’ensemble NP. Par contre, on n’a pas réussi à répondre à la question inverse : un problème dont la solution est facile à vérifier est-il oui ou non facile à résoudre ?

Par facile, on veut dire que la complexité de l’algorithme serait un polynôme, c’est-à-dire que le temps que prendra la méthode pour trouver la solution est proportionnel à une puissance de la taille du problème. L’avantage des polynômes, c’est que leurs temps de calcul est très rapide, en plus ça se combine très bien. Si on réalise un nombre polynomial d’opérations polynomiales, on reste en temps polynomial.

Notre polynôme peut grossir, mais il reste un polynôme. Ainsi, un problème est dans P s’il existe un algorithme pour le résoudre en temps polynômial. De même un problème est dans NP (Non-Déterministe Polynômial), s’il existe un algorithme pour vérifier qu’une solution donnée convient en un temps polynômial. En voici un exemple, considéré comme un des problèmes difficiles, celui du voyageur du commerce.

Pour vendre sa marchandise, le voyageur doit visiter plusieurs villes, reliées par un certain nombre de routes. Question : Pour une distance D, existe-t-il un trajet plus court que D permettant de visiter toutes les villes une et une seule fois par le voyageur ? Pour ce problème, on ne sait pas s’il existe un algorithme polynômial pour le résoudre. En revanche, si l’on donne un trajet, on peut vérifier immédiatement si ce trajet fait moins de D kms. Le problème est dans NP.

2- Problème P=NP ?

En 1956 Kurt Gödel, mathématicien autrichien, a demandé à John Von Neumann, célèbre scientifique américain, s’il pouvait trouver une solution rapide à un problème qui lui posait quelques difficultés. Quinze ans plus tard cette question a été généralisée par Stephen Cook, et a pris sa forme actuelle qui se trouve à mi-chemin entre l’informatique et les mathématiques. Une des questions formelles jamais posées par l’homme P=NP ? On peut la formuler ainsi : lorsqu’une solution à un problème est rapidement vérifiable, peut-elle être rapidement trouvée ?

Parmi l’ensemble des problèmes NP se trouvent des problèmes bien particuliers qu’on appelle les problèmes NP-complet. Un problème de classe NP-complet est un problème pour lequel le meilleur des algorithmes peut uniquement vérifier si une solution est correcte en temps polynomial. Le seul ennui, c’est le calcul de cette solution. Et là, c’est autre chose : généralement, le calcul de cette solution est très lent : il peut devenir impossible en pratique, même avec un ordinateur surpuissant ! La complexité du calcul peut ainsi devenir exponentielle ! Du moins, c’est ce qu’on remarque en pratique : on ne sait pas si on peut faire mieux théoriquement.

Une multitude de problèmes sont connus pour être NP-complets tels que le problème du sac à dos ou le problème du voyageur du commerce. Le problème des mots croisés en est un exemple aussi. Une liste de mots étant donnée, ainsi qu’une grille de mots croisés : peut-on mettre au point un algorithme intelligent qui permet de remplir la grille de mots croisés, avec les règles habituelles, en utilisant des mots parmi ceux de la liste ? Ce problème est NP, car avec de la chance, en plaçant les mots au hasard, on compose la grille cherchée. Il est NP-complet ainsi que l’a montré une étude de recherche scientifique.

Une propriété essentielle de ces problèmes NP-complet c’est que si pour un seul problème on trouve une méthode rapide pour le résoudre alors ça nous donnera une méthode rapide n’importe quel autre problème NP, car il serait possible de le transformer rapidement au premier facile à résoudre. Et c’est là tout l’intérêt d’étude des problèmes NP-complet.

Par conséquent, celui qui trouve un algorithme de complexité polynomiale pour résoudre, par exemple, le problème des grilles de mots croisés prouve que P = NP ; celui qui réussit à démontrer qu’il n’existe pas d’algorithmes rapides pour les grilles de mots croisés prouve que P ≠ NP (Fig. 2). Il n’y a pas de raison de croire que l’égalité P = NP soit vraie. L’attente de la plupart des informaticiens et mathématiciens est que l’égalité soit fausse. Malheureusement, il n’existe pas de preuve pour cette assertion.

3- Impact

Un des points fascinant du problème P=NP ? est l’existence de ces problèmes NP-complet et leur propriété de pouvoir représenter n’importe quel autre problème de leur classe NP. D’une certaine manière, c’est comme il s’agit fondamentalement du même problème mais qu’il existe plusieurs manières différentes de le voir.

Un autre point fascinant, est que s’il se trouve que P ≠ NP, alors ça veut dire qu’on peut avoir la méthode la plus intelligente, on serait fatalement obligé, lorsque l’énoncé deviendra très gros, de faire bêtement des essais, de tester et de revenir en arrière, on serait forcé d’explorer un arbre de choix arbitraire pour trouver une solution, notre méthode pourra certes éliminer beaucoup de possibilités, mais au final il nous restera beaucoup à tester une à une, et c’est ça la question du fond du problème P=NP ; Peut-on vraiment faire beaucoup mieux que de tester toutes les possibilités pour trouver une solution ? Cela signifierait qu’il est, fondamentalement, plus difficile de chercher la solution d’un problème que de vérifier cette solution.

Ça serait très surprenant si on arrive à prouver que P = NP. Ça aurait probablement de grosses conséquences, parce que ça indiquerait qu’on a une chance de résoudre des problèmes actuellement considérés comme difficiles  dans des temps acceptables. La sécurité de toutes nos données dépend de ce problème. Toute la science de la cryptographie, celle qui protège les échanges de données sur Internet ou permet à la carte de crédit d’être sécurisée, repose sur l’hypothèse que Non (P ≠ NP).

Quand on présente une clé de sécurité, il faut en effet qu’elle soit difficile à déchiffrer, mais facile à vérifier, sinon on pourrait attendre des heures avant que la page Internet sécurisée ne s’ouvre. Il s’agirait d’une totale remise en question de toute forme de sécurité sur internet car cela rendrait déchiffrables toutes les clés de cryptographie, si jamais P=NP. D’un autre côté, « tout » deviendrait moins cher, car les transports d’un point à un autre seront révolutionnés. Du côté des effets positifs de P ≠ NP, la cryptographie à clé publique et la sécurité bancaire seraient assurées.

4- Une question à 1 million de dollars !

Nous avons aujourd’hui de fortes raisons de croire que la question P = NP? soit d’une profonde difficulté. Les chercheurs estiment que la solution nécessitera l’introduction de nouvelles idées, ils considèrent que nous n’aurons pas la solution avant plusieurs années. Il s’agit de l’un des problèmes ouverts, un des plus célèbres, sinon le plus célèbre. Dans les années 2000, l’Institut de mathématiques Clay aux Etats Unis a constitué une liste de 7 problèmes particulièrement importants.

Les sept problèmes du millénaire, la question P=NP ? en est l’une des têtes d’affiche. Il y a toujours un million de dollars à qui sera en mesure de démontrer P = NP ou P ≠ NP. Un seul de ces sept problèmes a été résolu, la conjecture de Poincaré. Grigori Perelman, un mathématicien russe, l’a démontrée, ce qui lui a valu la médaille Fields (l’équivalent du Nobel en mathématiques) et le million de dollars en question ; il a décliné les deux ! Pour notre problème la question reste ouverte : Ce que nous pouvons trouver rapidement lorsque nous avons de la chance, peut-il être trouvé aussi vite par un calcul intelligent ?  ou encore l’intelligence peut-elle remplacer la chance ?

————————————————

(*) Pour avoir une idée sur la grandeur des puissances, rappelez-vous la légende du jeu d’échec. Pour remercier le sage qui inventa le jeu, le Roi accepte la récompense suivante : on plaça sur la première case de l’échiquier un grain de blé, 2 sur la deuxième, 4 sur la troisième, puis 8 et ainsi de suite en doublant le nombre de grains à chaque fois jusqu’à la 64ème case. Le Roi accepta, malgré ce qu’il pensait être comme une demande pleine d’humilité. Il se trouve qu’en réalité l’inventeur du jeu amassa au total (20+21+22+23+…+263 = 264-1 grains de blé) soit un équivalent d’environ 370 milliard de tonnes de blé. Ceci représente environ 1600 fois la production annuelle mondiale de blé en 2012 ! Il ne faut jamais sous-estimer les puissances et les exponentielles !

Commentaires:

Commentez...