TEMPS POLYNOMIAL

COMPLEXITÉ, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 627 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