Hiérarchie polynomiale - Définition
La hiérarchie polynômiale est une hiérarchie de classes de complexité de problèmes, qui étend la notion de classes P, NP, co-NP.
Définition
Quanteurs
On peut définir la hiérarchie à l'aide des quanteurs pour-tout et il-existe. Soit p un polynôme, et L un langage.
c'est-à-dire que 
quand il existe un mot w relativement petit (polynômialement) qui peut en témoigner. De la même façon on définit
On étend ces définition aux classes de langages : ainsi
Alors, on peut enfin donner les définitions des classes de la hiérarchie polynômiale par
En particulier, 
et 
.
Oracles
La hiérarchie polynômiale est également définissable à l'aide de machine de Turing avec oracle. AB dénote la classe des machines de complexité P augmentées d'un oracle de complexité B.
On pose
- Δ0P = Σ0P = Π0P = P
Puis pour tout i≥0 :
Populaires