Hiérarchie polynomiale

Représentation graphique de la hiérarchie polynomiale. Les flèches indiquent l'inclusion.

En théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP. La classe PH est l'union de toutes les classes de la hiérarchie polynomiale.

Définitions

Comme alternance de quantificateurs

On peut définir la hiérarchie à l'aide des quantificateurs universel () et existentiel (). Soit un polynôme, et un langage.

c'est-à-dire que quand il existe un mot relativement petit (polynomialement) qui peut en témoigner. De la même façon on définit

On étend ces définitions aux classes de langages : ainsi

Alors, on peut enfin donner les définitions des classes de la hiérarchie polynomiale par

En particulier, et .

Avec des machines à oracles

La hiérarchie polynomiale est également définissable à l'aide de machine de Turing avec oracle. dénote la classe des problèmes pouvant être résolus par des machines de complexité augmentées d'un oracle de complexité .

On pose

Puis pour tout i ≥ 0 :

Avec des machines alternantes

La hiérarchie polynomiale peut se définir à l'aide de machines de Turing alternantes. est la classe des langages décidés par une machine de Turing alternante en temps polynomial, dans laquelle toute exécution est composée de i suites de configurations de même type (existentielles ou universelles), la première suite ne contenant que des configurations existentielles. La définition de est similaire mais les configurations dans la première suite sont universelles.