COMPLEXITÉ, mathématique

Carte mentale

Élargissez votre recherche dans Universalis

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 n [...]

1  2  3  4  5
pour nos abonnés,
l’article se compose de 3 pages

Écrit par :

Classification

Autres références

«  COMPLEXITÉ, mathématique  » est également traité dans :

ALGORITHMIQUE

  • Écrit par 
  • Philippe COLLARD, 
  • Philippe FLAJOLET
  •  • 6 833 mots
  •  • 3 médias

Dans le chapitre « Échelle de complexité »  : […] L' étude précédente permet de situer divers problèmes algorithmiques sur une « échelle de complexité » présentée dans le tableau . Les diverses mesures de coût utilisées (opérations booléennes, opérations élémentaires sur les nombres réels, comparaisonséchanges) n'étant pas strictement équivalentes, la définition d'une telle échelle se précise par l'introduction d'un modèle de la notion de calcula […] Lire la suite

CALCUL, mathématique

  • Écrit par 
  • Philippe FLAJOLET
  •  • 1 782 mots

Dans le chapitre « Calculabilité et algorithmique »  : […] Dans les années 1930 s'élabore, sous l'impulsion notamment du logicien Alan Turing, une théorie abstraite de la calculabilité, ce avant même l'avènement de l'ordinateur. Tout n'est pas calculable en mathématique et, par exemple, il ne saurait exister de procédé systématique permettant de distinguer par calcul, parmi l'infini des assertions mathématiques possibles, celles qui sont vraies : il s'agi […] Lire la suite

KHOT SUBHASH (1978- )

  • Écrit par 
  • Bernard PIRE
  •  • 649 mots

Le mathématicien indien Subhash Khot est un théoricien de l’informatique, spécialiste des problèmes d’optimisation dans ce qu’il est convenu d’appeler la théorie de la complexité. Né le 10 juin 1978 à Ichalkaranji, ville moyenne de l’État du Maharashtra dans l’ouest de l’Inde, Khot est le fils de deux médecins. Classé premier au concours d’entrée de l’Institut indien de technologie (I.T.T.) de Bo […] Lire la suite

KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 561 mots

La théorie de la complexité de Kolmogorov d'une suite numérique S est définie comme la taille, K(S), du plus court programme P qui, confié à une machine universelle (tout ordinateur contemporain en est une), produit la suite S. Cette notion est séduisante car elle synthétise en un seul nombre plusieurs mesures de complexité dont celle que propose la théorie de l'information de l'Américain Claude […] Lire la suite

ONDELETTES

  • Écrit par 
  • Alexandre GROSSMANN, 
  • Bruno TORRESANI
  •  • 5 718 mots

Dans le chapitre « 3. Des algorithmes rapides »  : […] L'une des raisons essentielles du succès rencontré par les méthodes fondées sur la transformation de Fourier tient dans l'existence d'algorithmes rapides de calcul qui lui sont associés (la fameuse F.F.T. [Fast Fourier Transform]). Or il s'est avéré que les transformations en ondelettes discrètes, pour peu que l'ondelette soit convenablement choisie, sont naturellement associées à des algorithmes […] Lire la suite

Voir aussi

Pour citer l’article

Jean-Paul DELAHAYE, « COMPLEXITÉ, mathématique », Encyclopædia Universalis [en ligne], consulté le 15 août 2022. URL : https://www.universalis.fr/encyclopedie/complexite-mathematique/