Voir la source de Hiérarchie polynomiale

[[Image:Polynomial time hierarchy.svg|250px|thumb|droite|Représentation graphique de la hiérarchie polynomiale. Les flèches indiquent l'inclusion.]]

En [[théorie de la complexité des algorithmes|théorie de la complexité]], la '''hiérarchie polynomiale''' est une hiérarchie de [[Classe de complexité|classes de complexité]] qui étend la notion de classes [[P (complexité)|P]], [[NP (complexité)|NP]], [[co-NP]]. La classe '''[[PH (complexité)|PH]]''' est l'union de toutes les classes de la hiérarchie polynomiale.

== 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 (<math>\forall</math>) et existentiel (<math>\exists</math>). Tout d'abord, pour tout [[polynôme]] <math>p</math>, et tout langage <math>L</math>, on définit

: <math> \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\} </math>,

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

: <math> \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\} </math>.

On étend ces définitions aux classes de langages  <math>\mathcal C</math>  

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

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

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

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

=== Avec des machines à oracles ===
La hiérarchie polynomiale est également définissable à l'aide de [[machine de Turing]] avec [[oracle (machine de Turing)|oracle]]. <math>A^B</math> dénote la classe des problèmes pouvant être décidés par des machines de complexité <math>A</math> augmentées d'un oracle de complexité <math>B</math>.

On pose 

:<math>\Delta_0^P = \Sigma_0^P = \Pi_0^P = \mbox{P}</math>

Puis pour tout ''i'' ≥ 0 :

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

=== Avec des machines alternantes ===
La hiérarchie polynomiale peut se définir à l'aide de [[Machine de Turing alternante|machines de Turing alternantes]]. <math>\Sigma_{i}^P</math>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 <math>\Pi_{i}^P</math>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 <math>\Sigma_{2}^P</math><ref>{{Ouvrage|langue=en|auteur1=Sipser|titre=Introduction to computation theory|éditeur=|année=|pages totales=|isbn=}}</ref>.

Pour tout <math>i \geq 1</math>, le problème <math>\mathrm{SAT}_i</math>, défini comme le [[Problème SAT|problème de satisfabilité booléenne]] pour les formules propositionnelles en [[forme prénexe]] avec <math>i</math> quantificateurs alternant entre <math>\exists</math> et <math>\forall</math> et commençant par <math>\exists</math>, est complet pour <math>\Sigma_i^\mathrm{P}</math><ref>{{Référence Harvard sans parenthèses|Perifel|2014|p=200}}</ref>.

==Propriétés==

=== Question autour de l'effondrement ===

Une autre propriété importante, interne à la hiérarchie polynomiale, est la suivante : <math>\forall i, \Sigma_i^P = \Pi_i^P \Rightarrow \Sigma_i^P = \mathrm{PH}</math>, ce qui signifie que si à un niveau <math>i</math> deux classes sont égales, alors toutes les classes « au-dessus » sont égales. On parle alors d’« effondrement de la hiérarchie polynomiale au niveau <math>i</math> »<ref name=":0">{{Référence Harvard sans parenthèses|Perifel|2014|p=195}}</ref>.

On peut par exemple montrer que la hiérarchie polynomiale s'effondre si PH admet un problème complet<ref>{{Référence Harvard sans parenthèses|Perifel|2014|p=199}}</ref> ou si la [[hiérarchie booléenne]], qu'elle contient, s'effondre<ref>{{Article|prénom1=R.|nom1=Chang|prénom2=J.|nom2=Kadin|titre=The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection|périodique=SIAM Journal on Computing|volume=25|pages=340–354|date=1996-04-01|issn=0097-5397|doi=10.1137/S0097539790178069|lire en ligne=http://epubs.siam.org/doi/abs/10.1137/S0097539790178069|consulté le=2016-08-22}}</ref>. Dans ce dernier cas, elle s'effondre au niveau 3.

=== Liens avec les autres classes ===

On a l'inclusion : <math>\mathrm{PH} \subseteq \mathrm{PSPACE}</math><ref>{{Référence Harvard sans parenthèses|Perifel|2014|p=194}}</ref>. L'égalité entre PH et [[PSPACE]] n'est pas connue, elle impliquerait que la hiérarchie polynomiale s'effondre. En particulier, si <math>\mathrm{P} = \mathrm{NP}</math>, alors <math>\mathrm{NP} = \mathrm{coNP}</math>, c’est-à-dire <math>\Sigma_1^P = \Pi_1^P</math> : la hiérarchie polynomiale s’effondre au niveau 1<ref name=":0" />. 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 (complexité)|BPP]] est incluse dans le deuxième niveau de la hiérarchie polynomiale : <math>\mathrm{BPP} \subseteq \Sigma_2^P \cap \Pi_2^P</math>. Les relations entre PH et la classe de complexité quantique [[BQP]] ont aussi été étudiées<ref>
{{chapitre
 | langue = en
 | prénom = Scott | nom = Aaronson | lien auteur = Scott Aaronson
 | titre chapitre = BQP and the polynomial hierarchy
 | titre ouvrage = STOC
 | année = 2010
 | passage = 141-150}}.</ref>.

Le [[théorème de Toda]]<ref>{{Référence Harvard sans parenthèses|Perifel|2014|p=226}}</ref> é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 [[Sharp-P|♯P]] : <math>\mathrm{PH} \subseteq \mathrm{P}^{\sharp\mathrm{P}}</math>. Cet énoncé signifie que la classe de comptage <math>\sharp \mathrm{P}</math> est au moins aussi puissante que <math>\mathrm{PH}</math>.

Le [[théorème de Karp-Lipton]] énonce que si la classe [[NP (complexité)|NP]] est contenue dans la classe [[P/poly]], alors la hiérarchie polynomiale s'effondre au niveau 2<ref>{{Référence Harvard sans parenthèses|Perifel|2014|p=204}}</ref>.

== Bibliographie ==
* [[:en:Albert R. Meyer|A. R. Meyer]] and [[:en:Larry Stockmeyer|L. J. Stockmeyer]].  The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space.  ''In Proceedings of the 13th IEEE [[:en:Symposium on Switching and Automata Theory|Symposium on Switching and Automata Theory]]'', pp.&nbsp;125–129, 1972. L'article qui a introduit la hierarchie.
* [[:en:Larry Stockmeyer|L. J. Stockmeyer]]. [https://dx.doi.org/10.1016/0304-3975(76)90061-X The polynomial-time hierarchy]. ''[[Theoretical Computer Science]]'', vol.3, pp.&nbsp;1–22, 1976.
* {{Computational Complexity (Papadimitriou)}} Chap. 17. ''Polynomial hierarchy'', pp.&nbsp;409–438.
* {{Ouvrage|langue=en|auteur1=[[Michael R. Garey]]|auteur2=[[David S. Johnson]]|titre=[[:en:Computers and Intractability: A Guide to the Theory of NP-Completeness|Computers and Intractability : A Guide to the Theory of NP-Completeness]]|lieu=New York|éditeur=W.H. Freeman|année=1979|pages totales=338|passage=161–167|isbn=0-7167-1045-5|titre chapitre=Section 7.2: The Polynomial Hierarchy}}.
* {{Computational Complexity (Arora et Barak)|numéro chapitre=5|titre chapitre=The polynomial hierarchy and alternation}}
* {{Ouvrage|langue=fr|auteur1=Sylvain Perifel|titre=Complexité algorithmique|lieu=Paris|éditeur=Ellipses Marketing|collection=Références sciences|année=2014|pages totales=432|isbn=978-2-7298-8692-9|lire en ligne=http://www.liafa.univ-paris-diderot.fr/~sperifel/livre_complexite.html}}, chapitre 8 : la hiérarchie polynomiale.

==Lien externe==
*{{Complexity Zoo|fin=P#ph|nom=PH}}

== Voir aussi ==
* [[Hiérarchie booléenne]]
* [[NP (complexité)|NP]]
* [[PSPACE]]

==Références==
<references />

{{Traduction/Référence|en|Polynomial hierarchy|15883036}}

{{Palette|Théorie de la complexité}}

{{Portail|mathématiques|informatique théorique}}

{{DEFAULTSORT:Hierarchie Polynomiale}}
[[Catégorie:Logique mathématique]]
[[Catégorie:Théorie de la complexité des algorithmes]]
[[Catégorie:Classe de complexité]]