Hiérarchie polynomiale

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.

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

Définitions

Il existe plusieurs définitions équivalentes des classes de la hiérarchie polynomiale.

Comme alternance de quantificateurs

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

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

$\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\}$

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

$\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

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

On pose

$\Delta _{0}^{P}=\Sigma _{0}^{P}=\Pi _{0}^{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}}$

Avec des machines alternantes

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

Exemples de problèmes

Savoir si une formule de la logique propositionnelle est minimale, c'est-à-dire s'il n'existe pas de formules plus courtes équivalentes, est un problème algorithmique dans $\Sigma _{2}^{P}$.

Pour tout $i\geq 1$, le problème $\mathrm {SAT} _{i}$, défini comme le problème de satisfabilité booléenne pour les formules propositionnelles en forme prénexe avec $i$ quantificateurs alternant entre $\exists$ et $\forall$ et commençant par $\exists$, est complet pour $\Sigma _{i}^{\mathrm {P} }$.

Propriétés

Question autour de l'effondrement

Une autre propriété importante, interne à la hiérarchie polynomiale, est la suivante : $\forall i,\Sigma _{i}^{P}=\Pi _{i}^{P}\Rightarrow \Sigma _{i}^{P}=\mathrm {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$ ».

On peut par exemple montrer que la hiérarchie polynomiale s'effondre si PH admet un problème complet ou si la hiérarchie booléenne, qu'elle contient, s'effondre. Dans ce dernier cas, elle s'effondre au niveau 3.

Liens avec les autres classes

On a l'inclusion : $\mathrm {PH} \subseteq \mathrm {PSPACE}$. L'égalité entre PH et PSPACE n'est pas connue, elle impliquerait que la hiérarchie polynomiale s'effondre. En particulier, si $\mathrm {P} =\mathrm {NP}$, alors $\mathrm {NP} =\mathrm {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).

Le théorème de Sipser–Gács–Lautemann énonce que la classe probabiliste BPP est incluse dans le deuxième niveau de la hiérarchie polynomiale : $\mathrm {BPP} \subseteq \Sigma _{2}^{P}\cap \Pi _{2}^{P}$. Les relations entre PH et la classe de complexité quantique BQP ont aussi été étudiées.

Le théorème de Toda énonce que la hiérarchie polynomiale est incluse dans l'ensemble des problèmes résolubles en temps polynomial par une machine de Turing avec oracle pour la classe ♯P : $\mathrm {PH} \subseteq \mathrm {P} ^{\sharp \mathrm {P} }$. Cet énoncé signifie que la classe de comptage $\sharp \mathrm {P}$ est au moins aussi puissante que $\mathrm {PH}$.

Le théorème de Karp-Lipton énonce que si la classe NP est contenue dans la classe P/poly, alors la hiérarchie polynomiale s'effondre au niveau 2.

Bibliographie

• A. R. Meyer and L. J. Stockmeyer. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, pp. 125–129, 1972. L'article qui a introduit la hierarchie.
• L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, vol.3, pp. 1–22, 1976.
• (en) Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1993 (ISBN 978-0-201-53082-7) Chap. 17. Polynomial hierarchy, pp. 409–438.
• (en) Michael R. Garey et David S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, New York, W.H. Freeman, 1979, 338 p. (ISBN 0-7167-1045-5), « Section 7.2: The Polynomial Hierarchy », p. 161–167.
• (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 5 (« The polynomial hierarchy and alternation »)
• Sylvain Perifel, Complexité algorithmique, Paris, Ellipses Marketing, coll. « Références sciences », 2014, 432 p. (ISBN 978-2-7298-8692-9, lire en ligne), chapitre 8 : la hiérarchie polynomiale.

Lien externe

• (en) La classe PH sur le Complexity Zoo

Voir aussi

• Hiérarchie booléenne
• NP
• PSPACE

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Polynomial hierarchy » (voir la liste des auteurs).