Hiérarchie polynomiale

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
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 (\forall) et existentiel (\exists). Soit p un polynôme, et L un langage.

 \exists^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \exists w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\}

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

 \forall^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \forall w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\}

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

\exists^{\rm P} \mathcal{C} := \left\{ \exists^p L \ | \ p \mbox{ est un polynome et } L \in \mathcal{C} \right\}
\forall^{\rm P} \mathcal{C} := \left\{ \forall^p L \ | \ p \mbox{ est un polynome et } L \in \mathcal{C} \right\}

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

 \Sigma_0^{\rm P} := \Pi_0^{\rm P} := {\rm P}
 \Sigma_{k+1}^{\rm P} := \exists^{\rm P} \Pi_k^{\rm P}
 \Pi_{k+1}^{\rm P} := \forall^{\rm P} \Sigma_k^{\rm P}
 {\rm PH} = \underset{k\in \mathbb{N}}{\bigcup}\Sigma_{k}^{\rm P}

En particulier,  {\rm NP} = \Sigma_1^{\rm P} et  {\rm coNP} = \Pi_1^{\rm P} .

Avec des machines à oracles[modifier | modifier le code]

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

On pose

\Delta_0^P = \Sigma_0\mbox{P} = \Pi_0\mbox{P} = \mbox{P}

Puis pour tout i≥0 :

\Delta_{i+1}^P := \mbox{P}^{\Sigma_i^P}
\Sigma_{i+1}^P := \mbox{NP}^{\Sigma_i^P}
\Pi_{i+1}^P := \mbox{co-NP}^{\Sigma_i^P}

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

Classes déterministes[modifier | modifier le code]

On a l'inclusion : PH \scriptstyle \subseteq PSPACE.

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

En particulier, si P = NP, alors NP = coNP, c’est-à-dire \Sigma_1^P = \Pi_1^P : 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 : BPP \subseteq \Sigma_p^2 \cap \Pi_p^2, 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,‎ 2010, p. 141-150