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\rm{P} = \Sigma_0\mbox{P} = \Pi_0\mbox{P} = \mbox{P}

Puis pour tout i≥0 :

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

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

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

Et on a le lien suivant avec les classes probabilistes : BPP \scriptstyle \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]

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

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