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

Articles

• ALGORITHMIQUE

  • Écrit par Philippe COLLARD et Philippe FLAJOLET
  • 6 654 mots
  • 3 médias
  ...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.

• COMPLEXITÉ, mathématique

  • Écrit par Jean-Paul DELAHAYE
  • 1 626 mots
  ...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 constituent la classe de complexité P. On considère qu'un problème dans la classe P non seulement...