Anex:Classes de complexitat

Esta és una llista de classes de complexitat en teoria de la complexitat computacional.

Moltes d'estes classes tenen una co-classe que conté els problemes complementaris als de la classe original. Per eixemple, si L està en NP, el complement de L està en co-NP. Açò no significa que NP i co-NP siguen complementaris - hi ha problemes que pertanyen a abdós classes, i uns atres que no estan en cap de les dos.

Criteri de resolució temporal

P	Conta les solucions d'un problema de la classe NP
P-complet	Els problemes més difícils de P
AM	Resolubles en temps polinòmic en un protocol Arturo-Merlín.
BPP	Resolubles en temps polinòmic en un algoritme aleatori (en provabilitat d'error menor que 1/3)
BQP	Resolubles en temps polinòmic en una màquina quàntica (en resposta provablement correcta)
Co-NP	Sense respostes verificables en temps polinòmic
Co-NP-complet	Els problemes més difícils de co-NP
DTIME(f(n))	Resoluble per una màquina determinista en temps O(f(n)).
I	Resoluble en temps exponencial en exponent llineal
ELEMENTAL	L'unió de classes de la jerarquia exponencial
ESPACE	Resoluble en espai exponencial en exponent llineal
EXP	Igual que EXPTIME
EXPTIME	Resoluble en temps exponencial
FNP	Anàloga a NP per a problemes funcionals
FP	Anàloga a P per a problemes funcionals
FPNP	Anàloga a PNP per a problemes funcionals; esta classe conté al problema del viajante
IP	Resoluble en temps polinòmic en un sistema de demostració interactiu
MA	Resolubles en temps polinòmic en un protocol Merlín-Arturo
NC	Resoluble en temps polilogarítmico en màquines paraleles
NE	Resoluble en temps exponencial en exponent llineal per una màquina no determinista
NEXP	Igual a NEXPTIME
NEXPTIME	Resoluble en temps exponencial per una màquina no determinística
NP	Respostes positives verificables en temps polinòmic
NP-complet	Els més difícils problemes de NP
NP-fàcil	Anàlec a PNP per a problemes funcionals; també se li coneix com FPNP
NP-equivalent	Els problemes més difícils de FPNP
NP-hard	Problemes NP-difícils
NTIME(f(n))	Resoluble per una màquina no determinista en temps O(f(n)).
P	Resoluble en temps polinòmic
P-complet	Els problemes més difícils en P per a resoldre en màquines paraleles
PCP	Prova verificable probabilísticamente
PH	L'unió de les classes de la jerarquia polinòmica
PNP	Resoluble en temps polinòmic en un oràcul per a un problema en NP; també coneguda com Δ2P
PP	Polinòmic provabilístic (resposta correcta en provabilitat major a ½)
RP	Resoluble en temps polinòmic en un algoritme aleatori (resposta positiva correcta en provabilitat d'error menor a ½, resposta negativa exacta)
UP	Funcions polinòmiques no determinista no ambigües.
ZPP	Resoluble per algoritmes aleatoris (resposta sempre correcta, temps no acotat, en promig polinòmic)

Criteri de resolució espacial

DSPACE(f(n))	Resolubles en una màquina determinista en espai O(f(n)).
EXPSPACE	Resoluble en espai exponencial.
L	Resoluble en espai logarítmic.
NESPACE	Resoluble en espai exponencial en exponent llineal per una màquina no determinista.
NEXPSPACE	Resoluble per una màquina no determinista en espai exponencial.
NL	Resoluble per màquina no determinista en espai logarítmic.
NPSPACE	Resoluble per una màquina no determinista en espai polinòmic i temps illimitat.
NSPACE(f(n))	Resoluble per una màquina no determinista en espai O(f(n)).
PSPACE	Resoluble en espai polinòmic i temps illimitat.
PSPACE-complet	Els problemes més difícils de PSPACE.
SL	Resoluble per màquina no determinista en espai logarítmic, per a entrades particulars.

Enllaços externs

• [1] - Wiki que llista unes 400 classes de complexitat i les seues propietats.