Hiérarchie polynomiale
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (En mathématiques, un polynôme est la combinaison linéaire des puissances d'une variable, habituellement notée X. Ces objets sont largement utilisés en pratique, ne serait-ce que parce qu'ils donnent localement une valeur approchée...), 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 (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) 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}.

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é (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en...) P augmentées d'un oracle de complexité B.

On pose

Δ0P = Σ0P = Π0P = P

Puis pour tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) 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}}
Page générée en 0.527 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique