classe de complexité P
classe P
problème P
INFORMATIQUE
La classe de complexité P est la classe des problèmes de décision qui peuvent être résolus par un algorithme polynomial. Ces problèmes sont souvent considérés comme ceux pour lesquels il existe un algorithme efficace (voir la thèse de Cobham)
On dit qu’un problème est dans la classe P s’il existe un algorithme pour le résoudre en temps polynomial.