Hiérarchie polynomiale

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

La hiérarchie polynômiale est une hiérarchie de classes de complexité de problèmes, qui étend la notion de classes P, NP, co-NP.

[modifier] Définition

[modifier] 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 (polynômialement) 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 polynômiale 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} .

[modifier] Oracles

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

On pose

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