Hiérarchie polynomiale

On peut définir la hiérarchie à l'aide des quantificateurs universel (${\displaystyle \forall }$) et existentiel (${\displaystyle \exists }$). Tout d'abord, pour tout polynôme ${\displaystyle p}$, et tout langage ${\displaystyle L}$, on définit

${\displaystyle \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 l'ensemble ${\displaystyle \exists ^{p}L}$ contient exactement l'ensemble des mots ${\displaystyle x}$ pour lesquels il existe un mot ${\displaystyle w}$ de taille polynomiale en la longueur de x tel que le mot ${\displaystyle \langle x,w\rangle }$est dans ${\displaystyle L}$. Intuitivement, le mot ${\displaystyle w}$ joue le rôle d'un certificat pour ${\displaystyle x}$, certificat relativement petit par rapport à ${\displaystyle x}$. De la même façon on définit

${\displaystyle \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 ${\displaystyle {\mathcal {C}}}$

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

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

Maintenant, on peut définir les classes de la hiérarchie polynomiale par récurrence de la façon suivante :

${\displaystyle \Sigma _{0}^{\rm {P}}:=\Pi _{0}^{\rm {P}}:={\rm {P}}}$

${\displaystyle \Sigma _{k+1}^{\rm {P}}:=\exists ^{\rm {P}}\Pi _{k}^{\rm {P}}}$

${\displaystyle \Pi _{k+1}^{\rm {P}}:=\forall ^{\rm {P}}\Sigma _{k}^{\rm {P}}}$

${\displaystyle {\rm {PH}}={\underset {k\in \mathbb {N} }{\bigcup }}\Sigma _{k}^{\rm {P}}}$

En particulier, ${\displaystyle {\rm {NP}}=\Sigma _{1}^{\rm {P}}}$ et ${\displaystyle {\rm {coNP}}=\Pi _{1}^{\rm {P}}}$.

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

On pose

${\displaystyle \Delta _{0}^{P}=\Sigma _{0}^{P}=\Pi _{0}^{P}={\mbox{P}}}$

Puis pour tout i ≥ 0 :

${\displaystyle \Delta _{i+1}^{P}:={\mbox{P}}^{\Sigma _{i}^{P}}}$

${\displaystyle \Sigma _{i+1}^{P}:={\mbox{NP}}^{\Sigma _{i}^{P}}}$

${\displaystyle \Pi _{i+1}^{P}:={\mbox{co-NP}}^{\Sigma _{i}^{P}}}$

La hiérarchie polynomiale peut se définir à l'aide de machines de Turing alternantes. ${\displaystyle \Sigma _{i}^{P}}$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 ${\displaystyle \Pi _{i}^{P}}$est similaire mais les configurations dans la première suite sont universelles.

Une autre propriété importante, interne à la hiérarchie polynomiale, est la suivante : ${\displaystyle \forall i,\Sigma _{i}^{P}=\Pi _{i}^{P}\Rightarrow \Sigma _{i}^{P}=PH}$, ce qui signifie que si à un niveau ${\displaystyle 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 ${\displaystyle i}$ ».

On a l'inclusion : PH ${\displaystyle \scriptstyle \subseteq }$ PSPACE. L'égalité entre PH et PSPACE n'est pas connue. Mais l'égalité impliquerait que la hiérarchie polynomiale s'effondre.

En particulier, si ${\displaystyle P=NP}$, alors ${\displaystyle NP=coNP}$, c’est-à-dire ${\displaystyle \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).

Et on a le lien suivant avec la classe probabiliste BPP : ${\displaystyle 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[2].