Même à l’ère de l’IA, certains problèmes sont tout simplement trop difficiles à résoudre

Les ordinateurs ont progressé à pas de géant au cours des dernières décennies, mais cela ne signifie pas qu’ils peuvent tout résoudre.

Grâce aux technologies d’intelligence artificielle, les ordinateurs peuvent aujourd’hui engager des conversations convaincantes avec des personnes, composer des chansons, peindre des tableaux, jouer aux échecs et au go, et diagnostiquer des maladies, pour ne citer que quelques exemples de leurs prouesses technologiques.

Ces succès pourraient être considérés comme une indication que le calcul n’a pas de limites. Pour voir si c’est le cas, il est important de comprendre ce qui rend un ordinateur puissant.

La puissance d’un ordinateur comporte deux aspects : le nombre d’opérations que son matériel peut exécuter par seconde et l’efficacité des algorithmes qu’il exécute. La vitesse du matériel est limitée par les lois de la physique. Les algorithmes – essentiellement des ensembles d’instructions – sont écrits par des humains et traduits en une séquence d’opérations que le matériel informatique peut exécuter. Même si la vitesse d’un ordinateur pouvait atteindre la limite physique, des obstacles informatiques subsistent en raison des limites des algorithmes.

Ces obstacles comprennent des problèmes impossibles à résoudre par les ordinateurs et des problèmes qui sont théoriquement solubles mais qui, en pratique, dépassent les capacités des ordinateurs actuels, même les plus puissants, que l’on puisse imaginer. Les mathématiciens et les informaticiens tentent de déterminer si un problème est soluble en l’essayant sur une machine imaginaire.

Une machine à calculer imaginaire

La notion moderne d’algorithme, connue sous le nom de machine de Turing, a été formulée en 1936 par le mathématicien britannique Alan Turing. Il s’agit d’un dispositif imaginaire qui imite la façon dont les calculs arithmétiques sont effectués avec un crayon sur du papier. La machine de Turing est le modèle sur lequel tous les ordinateurs actuels sont basés.

Pour permettre des calculs qui nécessiteraient plus de papier s’ils étaient effectués manuellement, la réserve de papier imaginaire d’une machine de Turing est supposée être illimitée. Cela équivaut à un ruban imaginaire illimité, ou « bande », de carrés, dont chacun est soit vide, soit contient un symbole.

La machine est contrôlée par un ensemble fini de règles et démarre sur une séquence initiale de symboles sur le ruban. Les opérations que la machine peut effectuer sont le déplacement vers une case voisine, l’effacement d’un symbole et l’écriture d’un symbole sur une case vide. La machine calcule en effectuant une séquence de ces opérations. Lorsque la machine termine, ou « s’arrête », les symboles restant sur la bande constituent la sortie ou le résultat.

L’informatique concerne souvent des décisions dont la réponse est oui ou non. Par analogie, un test médical (type de problème) vérifie si l’échantillon d’un patient (une instance du problème) présente un certain indicateur de maladie (réponse par oui ou par non). L’instance, représentée dans une machine de Turing sous forme numérique, est la séquence initiale de symboles.

Un problème est considéré comme « soluble » s’il est possible de concevoir une machine de Turing qui s’arrête pour chaque instance, qu’elle soit positive ou négative, et qui détermine correctement la réponse de l’instance.

Tous les problèmes ne peuvent pas être résolus

De nombreux problèmes sont résolubles à l’aide d’une machine de Turing et peuvent donc être résolus sur un ordinateur, mais beaucoup d’autres ne le sont pas. Par exemple, le problème des dominos, une variante du problème des tuiles formulé par le mathématicien américain d’origine chinoise Hao Wang en 1961, n’est pas soluble.

La tâche consiste à utiliser un ensemble de dominos pour couvrir une grille entière et, selon les règles de la plupart des jeux de dominos, à faire correspondre le nombre de points sur les extrémités des dominos adjacents. Il s’avère qu’il n’existe aucun algorithme capable de partir d’un ensemble de dominos et de déterminer si cet ensemble couvrira complètement la grille ou non.

Rester raisonnable

Un certain nombre de problèmes solubles peuvent être résolus par des algorithmes qui s’arrêtent en un temps raisonnable. Ces « algorithmes en temps polynomial » sont des algorithmes efficaces, ce qui signifie qu’il est pratique d’utiliser des ordinateurs pour en résoudre les instances.

Des milliers d’autres problèmes solubles ne sont pas connus pour avoir des algorithmes en temps polynomial, malgré des efforts intensifs pour trouver de tels algorithmes. Parmi ces problèmes figure le problème du voyageur de commerce.

Le problème du voyageur de commerce consiste à savoir si un ensemble de points dont certains sont directement reliés, appelé graphe, possède un chemin qui part de n’importe quel point, passe par tous les autres points exactement une fois et revient au point d’origine. Imaginons qu’un vendeur veuille trouver un itinéraire qui passe par tous les foyers d’un quartier exactement une fois et revient au point de départ.

Ces problèmes, appelés NP-complets, ont été formulés indépendamment et leur existence a été démontrée au début des années 1970 par deux informaticiens, le Canadien américain Stephen Cook et l’Américain ukrainien Leonid Levin. Cook, dont les travaux sont arrivés en premier, a reçu pour ces travaux le prix Turing 1982, le plus élevé en informatique.

Le coût de la connaissance exacte

Les algorithmes les plus connus pour les problèmes NP-complets consistent essentiellement à rechercher une solution parmi toutes les réponses possibles. Le problème du voyageur de commerce sur un graphe de quelques centaines de points prendrait des années à être exécuté sur un superordinateur. De tels algorithmes sont inefficaces, ce qui signifie qu’il n’existe aucun raccourci mathématique.

Les algorithmes pratiques qui traitent ces problèmes dans le monde réel ne peuvent offrir que des approximations, bien que celles-ci s’améliorent. L’existence d’algorithmes efficaces en temps polynomial capables de résoudre des problèmes NP-complets figure parmi les sept problèmes ouverts du millénaire proposés par le Clay Mathematics Institute au début du XXIème siècle, chacun étant assorti d’un prix d’un million de dollars américains.

Au-delà de Turing

Une nouvelle forme de calcul pourrait-elle dépasser le cadre de Turing ? En 1982, le physicien américain Richard Feynman, lauréat du prix Nobel, a avancé l’idée d’un calcul basé sur la mécanique quantique.

En 1995, Peter Shor, un mathématicien appliqué américain, a présenté un algorithme quantique permettant de factoriser des entiers en temps polynomial. Les mathématiciens estiment que cette question est insoluble par les algorithmes en temps polynomial dans le cadre de Turing. La factorisation d’un nombre entier consiste à trouver un plus petit nombre entier supérieur à 1 qui peut diviser le nombre entier. Par exemple, le nombre entier 688.826.081 est divisible par un plus petit nombre entier 25.253, car 688.826.081 = 25.253 x 27.277.

Un algorithme majeur, l’algorithme RSA, largement utilisé pour sécuriser les communications en réseau, est basé sur la difficulté de factorisation des grands nombres entiers. Le résultat de Shor suggère que l’informatique quantique, si elle devient une réalité, changera le paysage de la cybersécurité.

Est-il possible de construire un ordinateur quantique à part entière pour factoriser des entiers et résoudre d’autres problèmes ? Certains scientifiques pensent que c’est possible. Plusieurs groupes de scientifiques dans le monde travaillent à la construction d’un tel ordinateur, et certains ont déjà construit des ordinateurs quantiques à petite échelle.

Néanmoins, comme toutes les nouvelles technologies inventées auparavant, il est presque certain que l’informatique quantique posera des problèmes qui imposeront de nouvelles limites.

 

yogaesoteric
27 juin 2023