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.^[1]

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 {\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 {\displaystyle \Delta _{i+1}^{\mathsf {P}}:={\mathsf {P}}^{\Sigma _{i}^{\mathsf {P}}}}}$

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

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

on ${\displaystyle {\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 {\displaystyle {\mathsf {NP}}^{\rm {A}}}}$ i ${\displaystyle {\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

${\displaystyle \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 {\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 {\displaystyle \exists ^{p}L}}$i la segona cadena w és un testimoni curt (${\displaystyle |w|\leq p(|x|}$) validant que x és un membre de ${\displaystyle \exists ^{p}L}$. En altres paraules, ${\displaystyle {\displaystyle \exists ^{p}L}}$ si i només si existeix un testimoni curt w tal que ${\displaystyle \langle x,w\rangle \in L}$. De forma similar es defineix

${\displaystyle \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:

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

${\displaystyle \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 ${\displaystyle {\mathsf {NP}}=\exists ^{\mathsf {P}}{\mathsf {P}}}$i ${\displaystyle {\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:

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

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

${\displaystyle \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

La definició implica les relacions

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

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

${\displaystyle \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 ${\displaystyle \Sigma _{k}^{\mathsf {P}}=\Sigma _{k+1}^{\mathsf {P}}}$o algun ${\displaystyle \Sigma _{k}^{\mathsf {P}}=\Pi _{k}^{\mathsf {P}}}$llavors la jerarquia col·lapsa al nivell k: per tot ${\displaystyle i>k}$${\displaystyle \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

Referències