Hiérarchie polynomiale

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.

Définition

Quanteurs

On peut définir la hiérarchie à l'aide des quanteurs pour-tout et il-existe. 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éfinition 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}$

En particulier, ${\rm NP} = \Sigma_1^{\rm P}$ et ${\rm coNP} = \Pi_1^{\rm P}$.

Oracles

La hiérarchie polynomiale est également définissable à l'aide de machine de Turing avec oracle. A^B dénote la classe des machines de complexité P augmentées d'un oracle de complexité B.

On pose

Δ₀P = Σ₀P = Π₀P = 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}}$

• (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)