Vés al contingut

Jerarquia polinòmica

De la Viquipèdia, l'enciclopèdia lliure

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

[modifica]

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

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

on é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. i 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

on é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 i la segona cadena w és un testimoni curt () validant que x és un membre de . En altres paraules, si i només si existeix un testimoni curt w tal que . De forma similar es defineix

Sigui C una classe de llenguatges. Es pot definir:

Les classes NP i co-NP es poden definir com i on P és la classe de complexitat P.

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

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

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

La definició implica les relacions

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 o algun llavors la jerarquia col·lapsa al nivell k: per tot . 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é

[modifica]

Referències

[modifica]