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

Articles

• ALGORITHMIQUE

  • Écrit par Philippe COLLARD, Philippe FLAJOLET
  • 6 652 mots
  • 3 médias
  ...Convenablement formalisée par référence à un modèle de calcul (par exemple le modèle de la machine de Turing), et à un codage standard des données, la relation (1) définit la notion de problème NP – c'est-à-dire résoluble en temps polynomial par une machine non déterministe. Les problèmes...

• COMPLEXITÉ, mathématique

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

• KHOT SUBHASH (1978- )

  • Écrit par Bernard PIRE
  • 651 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...