Hiérarchie polynomiale

Restez toujours informé : suivez-nous sur Google (☆)

Introduction

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.

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 := {x \in {0, 1}^{*} (\exists w \in {0, 1}^{\leq p (∣ x ∣)}) ⟨ x, w ⟩ \in L}

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 := {x \in {0, 1}^{*} (\forall w \in {0, 1}^{\leq p (∣ x ∣)}) ⟨ x, w ⟩ \in L}

On étend ces définition aux classes de langages : ainsi

\exists^{P} C := {\exists^{p} L ∣ p est un polynome et L \in C}

\forall^{P} C := {\forall^{p} L ∣ p est un polynome et L \in C}

Alors, on peut enfin donner les définitions des classes de la hiérarchie polynômiale par

Σ_{0}^{P} := Π_{0}^{P} := P

Σ_{k + 1}^{P} := \exists^{P} Π_{k}^{P}

Π_{k + 1}^{P} := \forall^{P} Σ_{k}^{P}

En particulier, $N P = Σ_{1}^{P}$ et $c o N P = Π_{1}^{P}$ .

Oracles

La hiérarchie polynômiale est également définissable à l'aide de machine de Turing avec oracle. A 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 :

Δ_{i + 1} P := P^{Σ_{i} P}

Σ_{i + 1} P := NP^{Σ_{i} P}

Π_{i + 1} P := co-NP^{Σ_{i} P}