Cette publication est accessible gratuitement
Lire

Définition de : COMPLEXITÉ, mathématique

De
6 pages
Article publié par Encyclopaedia Universalis COMPLEXITÉ, mathématique Au cœur de l'informatique théorique, la théorie du calcul – ou théorie de la calculabilité – née dans la décennie 1930 des travaux de Kurt Gödel (1906- 1978), Alan Turing (1912-1954) et Alonzo Church (1903-1995), répond à des questions sur ce qui est faisable dans l'absolu par le calcul avec un ordinateur. Elle énonce des résultats négatifs du type : il est impossible d'écrire un programme – aussi long et complexe soit-il – qui, chargé d'analyser d'autres programmes, repère ceux qui se perdent dans une boucle et ne se terminent jamais (indécidabilité de l'arrêt d'un programme). Ces preuves d'impossibilité sont importantes et une fine répartition entre ce qui est algorithmiquement faisable et ce qui ne l'est pas, est maintenant disponible. LLeess ccllaasssseess PP eett NNPP Ce domaine a ouvert la voie dans la décennie 1970 à une analyse d'un niveau plus fin, appelée théorie des classes de complexité, où l'on se pose des questions du type suivant : peut-on décomposer en facteurs premiers un nombre de n chiffres en utilisant un temps de calcul t majoré par un polynôme en n (on parle de temps polynomial) ? Les problèmes que l'on peut traiter en temps polynomial constituent la classe de complexité P. On considère qu'un problème dans la classe P non seulement est algorithmiquement traitable, mais qu'on peut le résoudre avec efficacité.
Voir plus Voir moins
COMPLEXITÉ, mathématique

Au cœur de l'informatique théorique, la théorie du calcul – ou théorie de la calculabilité – née dans la décennie 1930 des travaux de Kurt Gödel (1906-1978), Alan Turing (1912-1954) et Alonzo Church (1903-1995), répond à des questions sur ce qui est faisable dans l'absolu par le calcul avec un ordinateur. Elle énonce des résultats négatifs du type : il est impossible d'écrire un programme – aussi long et complexe soit-il – qui, chargé d'analyser d'autres programmes, repère ceux qui se perdent dans une boucle et ne se terminent jamais (indécidabilité de l'arrêt d'un programme). Ces preuves d'impossibilité sont importantes et une fine répartition entre ce qui est algorithmiquement faisable et ce qui ne l'est pas, est maintenant disponible.

Les classes P et NP

Ce domaine a ouvert la voie dans la décennie 1970 à une analyse d'un niveau plus fin, appelée théorie des classes de complexité, où l'on se pose des questions du type suivant : peut-on décomposer en facteurs premiers un nombre de n chiffres en utilisant un temps de calcul t majoré par un polynôme en n (on parle de temps polynomial) ? Les problèmes que l'on peut traiter en temps polynomial constituent la classe de complexité P. On considère qu'un problème dans la classe P non seulement est algorithmiquement traitable, mais qu'on peut le résoudre avec efficacité. Dans le cas contraire, on dit que le problème est intrinsèquement difficile. Bien sûr, connaître la classe de complexité P est important et de très nombreux travaux ont été menés dans ce but. En 2002 par exemple, des chercheurs indiens ont démontré un résultat attendu depuis deux décennies : le problème de savoir si un nombre est premier (problème de la primalité) est dans la classe P (le problème de la primalité n'est pas équivalent à celui de la décomposition en facteurs premiers, car on arrive parfois à savoir qu'un nombre n'est pas premier sans pour autant disposer d'aucun de ses facteurs non triviaux).

La question suivante a aussi été considérée : connaissant une éventuelle décomposition d'un nombre de n chiffres en facteurs non triviaux a et b, peut-on vérifier en temps polynomial qu'elle est correcte, c'est-à-dire que n = a.b ? La réponse ici est oui, car on sait effectuer la multiplication des deux nombres a et b en temps polynomial. Plus généralement, les problèmes dont on peut ainsi vérifier les solutions en temps polynomial constituent la classe NP. Le problème de la factorisation est dans la classe NP (d'après ce que nous venons de dire concernant la multiplication des entiers), en revanche on ignore si le problème de la factorisation est dans la classe P, et l'on pense généralement qu'il n'y est pas. C'est une question importante pour la cryptographie, où casser certains algorithmes cryptographiques est équivalent à factoriser des entiers.

Il semble intuitivement clair que la classe NP n'est pas identique à la classe P – car il est certainement plus facile de vérifier une solution proposée que de la rechercher ! Pourtant, la démonstration de l'affirmation P ≠ NP est l'une des énigmes les plus récalcitrantes de la théorie des classes de complexité. Un prix d'un million de dollars est offert pour qui prouvera ce résultat ou son opposé : P = NP. Il y a trente ans, on découvrait ce problème qu'on espérait résoudre rapidement ; en 2004, malgré de multiples tentatives – et le prix ! –, on cherche toujours en vain sa solution.

Cette situation de blocage est gênante, car elle se produit en un point central de la théorie de la complexité : tant que cette question ne sera pas proprement réglée, la théorie des classes de complexité sera entravée, et aucun des résultats dont on a besoin en cryptographie pour prouver de manière absolue la sûreté des méthodes les plus utilisées ne sera établi. Par exemple, démontrer que la factorisation ne peut pas être résolue en temps polynomial impliquerait P ≠ NP, et donc démontrer que la factorisation n'est pas polynomiale est plus difficile que démontrer que P ≠ NP. Tant que P ≠ NP résiste, il n'y a aucun espoir de prouver le résultat attendu en cryptographie sur la factorisation.

Le travail fait depuis trois décennies par les théoriciens des classes de complexité n'a cependant pas été vain, car un grand nombre de classes nouvelles ont été identifiées et comparées (souvent sans réussir à démontrer qu'elles étaient différentes deux à deux) et l'on dispose aujourd'hui d'un panorama très fin des échelles de complexité des problèmes, dont on doit espérer qu'il nous achemine vers le déblocage attendu.

La complexité algorithmique

Les difficultés mathématiques rencontrées sont peut-être liées aux résultats logiques d'incomplétude (démontrés par Gödel en 1930) et dont la compréhension n'a cessé de s'approfondir, en particulier grâce à la théorie de la complexité d'Andreï Kolmogorov (1903-1987), formulée simultanément en 1965 par Kolmogorov et Gregory Chaitin. Cette théorie dite de la complexité algorithmique développe mathématiquement l'idée qu'est complexe ce qui ne peut pas s'exprimer brièvement. Plus précisément, la complexité de Kolmogorov K(s) de la suite de caractères s est la taille du plus petit programme P qui engendre s. Cette théorie a connu des développements remarquables, conduisant en particulier à l'élucidation du problème de la définition mathématique des suites aléatoires, posé au début du xxe siècle. Cette solution formalise l'idée qu'est aléatoire ce qui est incompressible, c'est-à-dire ce qui ne peut se définir par une séquence de caractères plus courte que l'objet lui-même (une suite répétant mille fois les caractères 01 n'est pas aléatoire car on peut la définir par une séquence de caractères de longueur bien plus petite qu'elle-même, la séquence « mille fois 01 »). Un autre résultat de cette théorie est la découverte de la famille des nombres oméga de Chaitin. Ces nombres de complexité maximale concentrent en eux des propriétés étonnantes : ils sont transcendants, aléatoires et non calculables.

Autre succès de la théorie de la complexité de Kolmogorov : elle a établi des liens profonds avec la physique et pourrait bien être une clé de la thermodynamique statistique, comme Charles Bennett et Wojciech Zurek l'ont suggéré. Non seulement la compréhension du problème du coût énergétique minimum du calcul et des calculs réversibles s'appuie sur la théorie algorithmique de l'information, mais celle-ci joue un rôle clé dans une révolution dont tout laisse prévoir qu'elle occupera une place considérable dans l'avenir : l'introduction de la mécanique quantique en informatique.

L'idée est de considérer sérieusement que la meilleure théorie de notre monde physique est la mécanique quantique et non pas la mécanique classique. Sur cette nouvelle base, on s'intéresse alors à la physique du calcul et à la notion de calcul complexe. Auparavant, l'hypothèse implicite de toute l'informatique théorique était celle d'un monde newtonien. Cette hypothèse est moins bénigne qu'on ne le croyait et il a fallu admettre que de nombreux problèmes fondamentaux doivent être reformulés dans un monde quantique.

Citons deux résultats importants obtenus dans cette direction et qui ont bousculé nos connaissances sur la complexité. Le premier concerne la cryptographie, où l'intrusion de la mécanique quantique a permis de définir des protocoles d'échanges de clés secrètes dont la sûreté repose non plus sur des conjectures mathématiques non démontrées, mais simplement sur l'hypothèse de la validité des lois quantiques. Ces protocoles, qui utilisent des photons polarisés, ont été concrètement mis en œuvre ces dernières années et sont même commercialisés aujourd'hui. Le second résultat, obtenu en 1994 par Peter Shor, est la preuve qu'un ordinateur quantique peut réaliser la factorisation des entiers en temps polynomial (ce que, comme nous l'indiquions plus haut, un ordinateur classique ne peut vraisemblablement pas faire). Cette preuve a deux conséquences. D'abord, elle montre que l'introduction des modèles quantiques de calcul change profondément la situation en rendant possibles des traitements qui ne le sont pas dans le monde classique : dit brièvement, la notion de calcul complexe n'est pas la même dans un monde classique et dans un monde quantique. De nouvelles classes de complexité quantique sont donc venues compléter la famille commencée avec P et NP. La deuxième conséquence du résultat de Shor est que la mise au point de calculateurs quantiques, dont on ne sait pas aujourd'hui si elle aboutira, entraînerait des bouleversements graves en cryptographie.

On le voit, la théorie du calcul, qui a permis le développement à la fois de la théorie des classes de complexité et de la théorie algorithmique de la complexité, est soumise à de rapides et profondes évolutions. En permettant de formuler et d'étudier des versions précises et mathématisées des notions un peu vagues de problème complexe et d'objet complexe, elle se place au cœur de la science moderne.

Auteur: Jean-Paul DELAHAYE
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin