Anexo:Clases de complejidad

Esta es una lista de clases de complejidad en teoría de la complejidad computacional.^[1]

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 las 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.^[2]
BPP	Resolubles en tiempo polinómico con un algoritmo aleatorio (con probabilidad de error menor que ¹/₃)
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
FP^NP	Análoga a P^NP 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 P^NP para problemas funcionales; también se le conoce como FP^NP
NP-equivalente	Los problemas más difíciles de FP^NP
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
P^NP	Resoluble en tiempo polinómico con un oráculo para un problema en NP; también conocida como Δ₂P
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.

Referencias

↑ Goldreich, Oded (2010). Cambridge University Press, ed. P, NP, and NP-Completeness: The Basics of Complexity Theory.
↑ Sanjeev Arora, Boaz Barak (2009). Cambridge University Press; 1ª edición, ed. Computational Complexity: A Modern Approach. ISBN 978-0-521-42426-4.

Enlaces externos

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

Datos: Q1191786

[1] Goldreich, Oded (2010). Cambridge University Press, ed. P, NP, and NP-Completeness: The Basics of Complexity Theory.

[complex-2] Sanjeev Arora, Boaz Barak (2009). Cambridge University Press; 1ª edición, ed. Computational Complexity: A Modern Approach. ISBN 978-0-521-42426-4.

[1]

[2]