Jerarquia polinòmica

En teoria de la complexitat, la jerarquia polinòmica (de vegades dita jerarquia de temps polinòmic) és una jerarquia de classes de complexitat que generalitza les classes P, NP i co-NP a màquines oracle. És una contrapartida amb recursos fitats de la jerarquia aritmètica i la jerarquia analítica de lògica matemàtica.

Definicions

Hi ha múltiples definicions equivalents de les classes de la jerarquia polinòmica.

Per la definició de l'oracle de la jerarquia, es defineix

${\displaystyle \Delta _{0}^{\mathsf {P}}:=\Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}}}$

on P és el conjunt de problemes de decisió que es poden resoldre en temps polinòmic. Llavors per i ≥ 0 es defineix

${\displaystyle \Delta _{i+1}^{\mathsf {P}}:={\mathsf {P}}^{\Sigma _{i}^{\mathsf {P}}}}$

${\displaystyle \Sigma _{i+1}^{\mathsf {P}}:={\mathsf {NP}}^{\Sigma _{i}^{\mathsf {P}}}}$

${\displaystyle \Pi _{i+1}^{\mathsf {P}}:={\mathsf {coNP}}^{\Sigma _{i}^{\mathsf {P}}}}$

on ${\displaystyle {\mathsf {P}}^{\rm {A}}}$és el conjunt de problemes de decisió que es poden resoldre en temps polinòmic per una màquina de Turing amb un oracle per alguns problemes complets de la classe A. ${\displaystyle {\mathsf {NP}}^{\rm {A}}}$ i ${\displaystyle {\mathsf {coNP}}^{\rm {A}}}$es defineixen de forma anàloga.

Per la definició d'existència o universal de la jerarquia polinòmica, sigui L un llenguatge i p un polinomi, es defineix

$\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\}$

on ${\displaystyle \langle x,w\rangle \in \{0,1\}^{*}}$és qualsevol codificació d'un parell de les cadenes binaries x i w en una sola cadena. L representa un conjunt ordenat de parelles de cadenes, on la primera cadena x és un membre de ${\displaystyle \exists ^{p}L}$i la segona cadena w és un testimoni curt ($|w|\leq p(|x|$) validant que x és un membre de $\exists ^{p}L$. En altres paraules, ${\displaystyle \exists ^{p}L}$ si i només si existeix un testimoni curt w tal que $\langle x,w\rangle \in L$. De forma similar es defineix

$\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\}$

Sigui C una classe de llenguatges. Es pot definir:

$\exists ^{\mathsf {P}}{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p{\text{ és un polinomi i}}L\in {\mathcal {C}}\right\}$

$\forall ^{\mathsf {P}}{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\text{ és un polinomi i}}L\in {\mathcal {C}}\right\}$

Les classes NP i co-NP es poden definir com ${\mathsf {NP}}=\exists ^{\mathsf {P}}{\mathsf {P}}$i ${\mathsf {coNP}}=\forall ^{\mathsf {P}}{\mathsf {P}}$on P és la classe de complexitat P.

La jerarquia polinòmica es pot definir de forma recursiva com:

$\Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}}$

$\Sigma _{k+1}^{\mathsf {P}}:=\exists ^{\mathsf {P}}\Pi _{k}^{\mathsf {P}}$

$\Pi _{k+1}^{\mathsf {P}}:=\forall ^{\mathsf {P}}\Sigma _{k}^{\mathsf {P}}$

Aquesta definició mostra la estreta relació entre la jerarquia polinòmica i la jerarquia aritmètica, on R i RE tenen un paper anàleg a P i NP respectivament. La jerarquia analítica també es pot definir d'una forma similar per donar una jerarquia de subconjunts dels nombres reals.

Relacions entre classes de la jerarquia polinòmica

Diagrama equivalent a la jerarquia polinòmica. Les fletxes volen dir inclusió.

La definició implica les relacions

$\Sigma _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Sigma _{i+1}^{\mathsf {P}}$

$\Pi _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Pi _{i+1}^{\mathsf {P}}$

$\Sigma _{i}^{\mathsf {P}}={\mathsf {co}}\Pi _{i}^{\mathsf {P}}$

A diferència de les jerarquies aritmètica i analítica, les inclusions no se sap si son pròpies, sent encara una qüestió oberta, tot i que se suposa que ho son.

Si algun $\Sigma _{k}^{\mathsf {P}}=\Sigma _{k+1}^{\mathsf {P}}$o algun $\Sigma _{k}^{\mathsf {P}}=\Pi _{k}^{\mathsf {P}}$llavors la jerarquia col·lapsa al nivell k: per tot $i>k$$\Sigma _{i}^{\mathsf {P}}=\Sigma _{k}^{\mathsf {P}}$. En concret, si P = NP llavors la jerarquia col·lapse completament.

La unió de totes les classes de la jerarquia polinòmica és la classe de complexitat PH.

Vegeu també

• EXPTIME
• Jerarquia exponencial
• Jerarquia aritmètica