P (complexité)
classe de complexité des algorithmes / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur P (complexité)?
Résumez cet article pour un enfant de 10 ans
Pour les articles homonymes, voir Classe P.
La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques. Par définition, un problème de décision est dans P s'il est décidé par une machine de Turing déterministe en temps polynomial par rapport à la taille de l'entrée. On dit que le problème est décidé en temps polynomial.
Les problèmes dans P sont considérés comme « faisables » (feasible en anglais), faciles à résoudre (dans le sens où on peut le faire relativement rapidement). C'est la thèse de Cobham émise par le scientifique américain Alan Cobham[1],[2]. René Lalement attribue cette thèse à Cook[3]. La classe P est incluse dans la classe NP, conduisant à l'un des grands problèmes ouverts de la théorie de la complexité, à savoir : P est-il égal à NP ?