Que donneriez-vous pour avoir un million de dollars ?
Je serais prêt à donner beaucoup.
Je rêve de longues nuits pleines de sommeil en ayant cette somme sur mon compte en banque. Pour l'obtenir, je pourrais par exemple braquer une banque, avoir de la chance et réussir en affaires, empoisonner mes parents subrepticement ou simplement résoudre le problème P contre NP.
Si vous résolvez l’équation, le Clay Mathematics Institute vous gratifiera immédiatement d’au moins cette somme.
Le problème est que les plus grands mathématiciens de notre planète n’y parviennent pas avec pour conséquence de implications colossales dans l’essor de l'intelligence artificielle et de ses applications.
Je ne suis pas professeur et encore moins amateur de mathématiques pures ou d’informatique et vous allez devoir lire ce qui suit en sachant que j'ai dû demander où il fallait écrire mon nom sur mon examen de math de niveau O. Cependant, qui ne tente rien, n’a rien alors, continuons.
La clé de tout cette histoire, ce sont les algorithmes.
Ce sont eux qui nous permettent de créer une intelligence artificielle. Un algorithme est difficile à définir, mais il s'agit généralement d'un ensemble d'instructions dynamiques et interactives utilisées pour résoudre des problèmes par des "êtres" intelligents artificiels, comme des ordinateurs ou des robots.
Si ces êtres peuvent résoudre de nombreux problèmes par déduction et processus algorithmiques, ils doivent le faire dans un délai raisonnable. Je peux certainement me mettre à peindre le pont Forth (dont on dit qu'il doit être repeint depuis le début une fois terminé car il met le temps de son rafraîchissement à se détériorer), mais le temps qu'il me faudrait pour y parvenir serait bien trop long pour être utile, viable ou même répété.
De la même manière, les algorithmes doivent résoudre leurs problèmes dans un temps polynomial, P, qui a une fin et est utile, et non en un temps polynomial non déterministe, NP, qui est en fait éternel. En effet, bien que nous sachions que l'algorithme est sur le bon chemin, nous mourrons certainement avant de connaître la réponse.
Le concept a été exploré par Douglas Adams dans le Guide de la galaxie de l'auto-stoppeur, dans lequel le super-ordinateur Deep Thought passe sept millions et demi d'années à trouver la réponse à la question ultime. Malheureusement, nous ne savons pas quelle était la question, mais nous savons que le processus a montré que NP n'était pas égal à P.
D'autres exemples de ce défi sont tout à fait ahurissants. Prenons, par exemple, la fameuse énigme du voyageur de commerce. Il est impossible pour un algorithme de déterminer rapidement le chemin le plus court pour qu’un représentant ne se rende dans toutes les villes de son itinéraire qu’une seule fois et revienne ensuite à son point de départ.
Pourquoi est-ce impossible ?
Eh bien, parce qu'il faut à un algorithme passer par environ mille étapes pour résoudre ce problème avec seulement dix villes. Si nous considérons vingt villes, cela fait plus d'un million d’étapes. Imaginons que notre vendeur doive faire appel à cette technologie pour les trois cents villes les plus peuplées des États-Unis, l'algorithme y serait encore au moment où nous aurions quitté Saturne pour vivre sur Pluton et j'aurais bien sûr, hérité de mes parents plusieurs millions d'ici là, c'est déjà ça.
Un autre exemple étrange.
C'est l’heureux moment d’un mariage. Notre jeune couple a quarante-huit invités qui le célébreront avec lui dans quelques mois. Les futurs mariés ont bien sûr besoin d’asseoir les convives de façon optimale. Tous devront être placés près de leur famille ou de leurs amis et personne ne devra avoir envie d’attaquer son voisin avec le couteau à poisson.
Compte tenu de la liste des participants, de leurs préférences et des éléments liés aux tables, comme la présence obligatoire à une certaine table ou le nombre de personnes pouvant s'asseoir à chacune d'elles, un algorithme ne pourra jamais déterminer complètement la disposition idéale des sièges.
Une fois de plus, vous vous demandez pourquoi.
D’abord, l’algorithme devra prendre en considération plus de trois cent millions d'options possibles rien que pour la première table de huit personnes pour un placement de table de quarante-huit personnes. Il devra ensuite traiter plus de septante-cinq millions d'options pour la table suivante, et ainsi de suite. Au moment où le plan sera complètement terminé, le couple sera peut-être non seulement divorcé mais surtout mort depuis des millénaires.
Il existe de nombreux autres exemples de problèmes que les algorithmes ne peuvent jamais résoudre complètement, de la simple grille de sudoku jusqu'à la raison pour laquelle je suis toujours surpris lorsque mon imprimante imprime réellement. Nous savons lorsque l'algorithme fonctionne correctement et pouvons très rapidement vérifier que la solution est effectivement correcte à la toute fin, mais pour eux, passer de NP à P - du conceptuel à l’utile - est encore impossible à ce jour.
Résolvez P contre NP, et vous gagnerez un million. Résolvez le défi P contre NP et vous changerez le monde pour toujours.
Et vous serez bien plus que millionnaire.
photo par Karolina Grabowska
