COMPLEXITÉ, mathématique

Carte mentale

Élargissez votre recherche dans Universalis

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


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 831 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 25 novembre 2020. URL : https://www.universalis.fr/encyclopedie/complexite-mathematique/