Hiérarchie polynomiale

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques image illustrant l’informatique théorique
Cet article est une ébauche concernant les mathématiques et l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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[modifier | modifier le code]

Comme alternance de quantificateurs[modifier | modifier le code]

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[modifier | modifier le code]

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 :

Propriétés[modifier | modifier le code]

Classes déterministes[modifier | modifier le code]

On a l'inclusion : PH PSPACE.

Une autre propriété importante, interne à la hiérarchie polynomial est la suivante : , ce qui signifie que si à un niveau deux classes sont égales, alors toutes les classes « au-dessus » sont égales. On parle alors d’« effondrement de la hiérarchie polynomiale au niveau  ».

En particulier, si , alors , c’est-à-dire  : la hiérarchie polynomiale s’effondre au niveau 1. On ne pense donc pas que la hiérarchie polynomiale s’effondre au niveau 1 (c’est la question P=NP).

Classes probabilistes[modifier | modifier le code]

Et on a le lien suivant avec la classe probabiliste BPP : , c'est le théorème de Sipser–Gács–Lautemann. Les relations entre PH et la classe de complexité quantique BQP ont aussi été étudiées[1].

Bibliographie[modifier | modifier le code]

Lien externe[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

  1. Scott Aaronson, « BQP and the polynomial hierarchy », dans STOC, , p. 141-150