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.

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 () et existentiel (). Tout d'abord, pour tout polynôme , et tout langage , on définit

 ,

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

 .

On étend ces définitions aux classes de langages    

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

En particulier,  et .

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

On pose 

Puis pour tout i ≥ 0 :

Avec des machines alternantes 
La hiérarchie polynomiale peut se définir à l'aide de machines de Turing alternantes. 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 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 .

Propriétés

Question autour de l'effondrement 

Une autre propriété importante, interne à la hiérarchie polynomiale, est la suivante : , ce qui signifie que si à un niveau  deux classes sont égales, alors toutes les classes « au-dessus » sont égales. On parle alors d’« effondrement de la hiérarchie polynomiale au niveau  ».

On a l'inclusion : PH  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 , alors , c’est-à-dire  : 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 

Et on a le lien suivant avec la classe probabiliste BPP : , 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.

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.
  Chap. 17. Polynomial hierarchy, pp. 409–438.
 .

Lien externe

Voir aussi 
 Hiérarchie arithmétique

Références

Logique mathématique
Théorie de la complexité des algorithmes
Classe de complexité