Classe P

Définition

La classe P (Polynomial time) regroupe l’ensemble des problèmes de décision qui peuvent être résolus en temps polynomial par un algorithme déterministe.

$$P=\{Q\mid \exists A\text{ deˊterministe et polynomial tel que }A\text{ deˊcide }Q\}$$

Autrement dit, pour une instance d’entrée de taille $n$, l’algorithme s’exécute en $O(n^k)$ pour une constante $k$.

Exemples

• 2-SAT
• Tri fusion
• Recherche dans un graphe (BFS, DFS)
• Problème du plus court chemin (Dijkstra, Bellman-Ford)

Propriétés

• $P$ est inclus dans Classe NP :
  $P\subseteq NP$
• $P$ est égal à sa classe complémentaire :
  $P=co\text{-}P$