Anexo:Clases de complejidad

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.

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • Clases de complejidad — Anexo:Clases de complejidad 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 …   Wikipedia Español

  • Anexo:Episodios de Numb3rs — La siguiente es una lista de episodios de la serie norteamericana NUMB3RS. Contenido 1 Estrenos y Lanzamientos en DVD 2 Primera temporada (2005) 3 Segunda temporada (2005 2006) …   Wikipedia Español

  • Clase de complejidad — En teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada. Una clase de complejidad tiene una definición de la forma: el conjunto de los problemas de decisión que pueden …   Wikipedia Español

  • Anexo:Sesgos cognitivos — El hombre en el centro ha cometido un error en sus pasos de baile, y choca contra la mujer, que se enoja y los demás murmuran. En la obra de Jane Austen Orgullo y prejuicio (1813) se muestra claramente el prejuicio de clases sociales y cómo el… …   Wikipedia Español

  • Anexo:Matemáticos importantes — En esta lista de matemáticos importantes se presenta una selección de matemáticos desde la antigüedad hasta el presente. La selección se orienta por los aportes científicos, utilizando como criterio para definir el grado de notoriedad la atención …   Wikipedia Español

  • Anexo:Personajes de Neon Genesis Evangelion — Neon Genesis Evangelion es un anime de 26 episodios, producidos por el estudio Gainax, ya finalizado, y un manga aún en publicación. Además de su temática épica y futurista, la serie está marcada por un gran número de personajes de gran… …   Wikipedia Español

  • Anexo:Personajes de Bob Esponja — Esta es la lista de los personajes de la serie animada Bob Esponja por Nickelodeon. Contenido 1 Personajes principales 1.1 Bob Esponja 1.2 Patricio 1.3 Calamardo …   Wikipedia Español

  • Anexo:Episodios de Dragon Ball — Esta es una lista de episodios del anime Dragon Ball, primera de las tres series derivadas del manga con el mismo nombre. Este anime fue producido por Toei Animation y estrenado en Japón en Fuji TV desde el 26 de febrero de 1986 hasta el 12 de… …   Wikipedia Español

  • Anexo:Civilizaciones con tradición notable en el Tiro con arco — Se puede hablar principalmente de dos tradiciones de tiro con arco, por un lado la tradición asiática, y por otro la mediterránea (u occidental), donde los elementos diferenciadores son, más que los puramente geográficos, la tecnología de… …   Wikipedia Español

  • Anexo:Terminología de la ciencia-ficción — En la ciencia ficción es frecuente el uso de terminología especializada, jerga fantástico científica. Sin embargo, no están creadas como una forma de lenguaje identificativo, sino que la mayor parte de las veces son ideas y conceptos interesantes …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”