P PROBLÈME, théorie de la complexité

ALGORITHMIQUE

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

Dans le chapitre « Algorithmes combinatoires »  : […] Entrent dans la catégorie des problèmes combinatoires , en informatique, les problèmes qui consistent à déterminer, pour une donnée  d , si est satisfaite une condition : où : ( a ) S( d ) est l'espace de recherche (l'espace des solutions potentielles) de taille exponentielle en la taille de d  ; ( b ) Q est une condition facilement vérifiable algo […] Lire la suite☛ http://www.universalis.fr/encyclopedie/algorithmique/#i_56170

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 pro […] Lire la suite☛ http://www.universalis.fr/encyclopedie/complexite-mathematique/#i_56170