Anexo:Clases de complejidad

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Esta es la lista de clases de complejidad en teoría de la complejidad computacional.

Muchas de estas clases tienen una co-clase que contiene los problemas complementarios a los de la clase original. Por ejemplo, si L está en NP, el complemento de L está en co-NP. Esto no significa que NP y co-NP sean complementarios - hay problemas que pertenecen a ambas clases, y otros que no están en ninguna de los dos.


Criterio de resolución temporal[editar]

#P Cuenta las soluciones de un problema de la clase NP
#P-completo Los problemas más difíciles de #P
AM Resolubles en tiempo polinómico con un protocolo Arturo-Merlín
BPP Resolubles en tiempo polinómico con un algoritmo aleatorio (con probabilidad de error menor que 1/3)
BQP Resolubles en tiempo polinómico en una máquina cuántica (con respuesta probablemente correcta)
Co-NP Sin respuestas verificables en tiempo polinómico
Co-NP-completo Los problemas más difíciles de co-NP
DTIME(f(n)) Resoluble por una máquina determinista en tiempo O(f(n)).
E Resoluble en tiempo exponencial con exponente lineal
ELEMENTAL La unión de clases de la jerarquía exponencial
ESPACE Resoluble en espacio exponencial con exponente lineal
EXP Igual que EXPTIME
EXPTIME Resoluble en tiempo exponencial
FNP Análoga a NP para problemas funcionales
FP Análoga a P para problemas funcionales
FPNP Análoga a PNP para problemas funcionales; esta clase contiene al problema del viajante
IP Resoluble en tiempo polinómico con un sistema de demostración interactivo
MA Resolubles en tiempo polinómico con un protocolo Merlín-Arturo
NC Resoluble en tiempo polilogarítmico en máquinas paralelas
NE Resoluble en tiempo exponencial con exponente lineal por una máquina no determinista
NEXP Igual a NEXPTIME
NEXPTIME Resoluble en tiempo exponencial por una máquina no determinística
NP Respuestas positivas verificables en tiempo polinómico
NP-completo Los más difíciles problemas de NP
NP-fácil Análogo a PNP para problemas funcionales; también se le conoce como FPNP
NP-equivalente Los problemas más difíciles de FPNP
NP-hard Problemas NP-difíciles
NTIME(f(n)) Resoluble por una máquina no determinista en tiempo O(f(n)).
P Resoluble en tiempo polinómico
P-completo Los problemas más difíciles en P para resolver en máquinas paralelas
PCP Prueba verificable probabilísticamente
PH LA unión de las clases de la jerarquía polinómica
PNP Resoluble en tiempo polinómico con un oráculo para un problema en NP; también conocida como Δ2P
PP Polinómico probabilístico (respuesta correcta con probabilidad mayor a ½)
RP Resoluble en tiempo polinómico con un algoritmo aleatorio (respuesta positiva correcta con probabilidad de error menor a ½, respuesta negativa exacta)
UP Funciones polinómicas no deterministas no ambiguas.
ZPP Resoluble por algoritmos aleatorios (respuesta siempre correcta, tiempo no acotado, en promedio polinómico)

Criterio de resolución espacial[editar]

DSPACE(f(n)) Resolubles con una máquina determinista en espacio O(f(n)).
EXPSPACE Resoluble en espacio exponencial.
L Resoluble en espacio logarítmico.
NESPACE Resoluble en espacio exponencial con exponente lineal por una máquina no determinista.
NEXPSPACE Resoluble por una máquina no determinista en espacio exponencial.
NL Resoluble por máquina no determinista en espacio logarítmico.
NPSPACE Resoluble por una máquina no determinista en espacio polinómico y tiempo ilimitado.
NSPACE(f(n)) Resoluble por una máquina no determinista en espacio O(f(n)).
PSPACE Resoluble en espacio polinómico y tiempo ilimitado.
PSPACE-completo Los problemas más difíciles de PSPACE.
SL Resoluble por máquina no determinista en espacio logarítmico, para entradas particulares.

Enlaces externos[editar]

  • qwiki.caltech.edu - Wiki que lista unas 400 clases de complejidad y sus propiedades.