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 »  : […] des recherches algorithmiques, aucun algorithme n'a été trouvé qui permette de résoudre l'un quelconque de ces problèmes en un temps polynomial en la taille des données d'entrées. Ce fait donne lieu à la célèbre conjecture :dans laquelle P désigne la classe des problèmes résolubles en temps polynomial […] 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 »  : […] t majoré par un polynôme en n (on parle de temps polynomial) ? Les problèmes que l'on peut traiter en temps polynomial constituent la classe de complexité P. On considère qu'un problème dans la classe P non seulement est algorithmiquement traitable, mais qu'on peut le résoudre avec efficacité. Dans le cas contraire, on dit que le problème est […] Lire la suite☛ http://www.universalis.fr/encyclopedie/complexite-mathematique/#i_56170