# 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

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

## Referències

* ↑ Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264.