NP 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 algorithmiquement (c'est-à-dire en un temps polynomial […] Lire la suite

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

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