- Anexo:Clases de complejidad
-
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
#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
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
- qwiki.caltech.edu - Wiki que lista unas 400 clases de complejidad y sus propiedades.
Categorías:- Anexos:Informática
- Clases de complejidad
Wikimedia foundation. 2010.
