« COMPLEXITÉ THÉORIE DES CLASSES DE »

COMPLEXITÉ, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 626 mots

Dans le chapitre "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 c […] Lire la suite

Recevez les offres exclusives Universalis