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

${\mathrm{\Delta }}_0^{𝖯}:={\mathrm{\Sigma }}_0^{𝖯}:={\mathrm{\Pi }}_0^{𝖯}:=𝖯$

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

${\mathrm{\Delta }}_{i+1}^{𝖯}:={𝖯}^{{\mathrm{\Sigma }}_i^{𝖯}}$

${\mathrm{\Sigma }}_{i+1}^{𝖯}:={𝖭𝖯}^{{\mathrm{\Sigma }}_i^{𝖯}}$

${\mathrm{\Pi }}_{i+1}^{𝖯}:={𝖼𝗈𝖭𝖯}^{{\mathrm{\Sigma }}_i^{𝖯}}$

on ${𝖯}^{\mathrm{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. ${𝖭𝖯}^{\mathrm{A}}$ i ${𝖼𝗈𝖭𝖯}^{\mathrm{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

${\mathrm{\exists }}^{p}L:=\{x\in \{0,1{\}}^{*}|(\mathrm{\exists }w\in \{0,1{\}}^{\le p(|x|)})⟨x,w⟩\in L\}$

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

${\mathrm{\forall }}^{p}L:=\{x\in \{0,1{\}}^{*}|(\mathrm{\forall }w\in \{0,1{\}}^{\le p(|x|)})⟨x,w⟩\in L\}$

Sigui C una classe de llenguatges. Es pot definir:

${\mathrm{\exists }}^{𝖯}𝒞:=\{{\mathrm{\exists }}^{p}L|p\text{ és un polinomi i}L\in 𝒞\}$

${\mathrm{\forall }}^{𝖯}𝒞:=\{{\mathrm{\forall }}^{p}L|p\text{ és un polinomi i}L\in 𝒞\}$

Les classes NP i co-NP es poden definir com $𝖭𝖯={\mathrm{\exists }}^{𝖯}𝖯$i $𝖼𝗈𝖭𝖯={\mathrm{\forall }}^{𝖯}𝖯$on P és la classe de complexitat P.

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

${\mathrm{\Sigma }}_0^{𝖯}:={\mathrm{\Pi }}_0^{𝖯}:=𝖯$

${\mathrm{\Sigma }}_{k+1}^{𝖯}:={\mathrm{\exists }}^{𝖯}{\mathrm{\Pi }}_k^{𝖯}$

${\mathrm{\Pi }}_{k+1}^{𝖯}:={\mathrm{\forall }}^{𝖯}{\mathrm{\Sigma }}_k^{𝖯}$

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

${\mathrm{\Sigma }}_i^{𝖯}\subseteq {\mathrm{\Delta }}_{i+1}^{𝖯}\subseteq {\mathrm{\Sigma }}_{i+1}^{𝖯}$

${\mathrm{\Pi }}_i^{𝖯}\subseteq {\mathrm{\Delta }}_{i+1}^{𝖯}\subseteq {\mathrm{\Pi }}_{i+1}^{𝖯}$

${\mathrm{\Sigma }}_i^{𝖯}=𝖼𝗈{\mathrm{\Pi }}_i^{𝖯}$

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