Clases de complejidad

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
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)).
Espacio logarítmico Resoluble en espacio logarítmico
ESPACIOP Resoluble en espacio polinómico y tiempo ilimitado
ESPACIOP-completo Los problemas más difíciles de ESPACIOP
ESPACIONP Resoluble por una máquina no-determinista en espacio polinómico y tiempo ilimitado
EXPSPACE Resoluble en espacio exponencial
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 Igual que ESPACIONP
NSPACE(f(n)) Resoluble por una máquina no-determinista en espacio O(f(n)).
PSPACE Igual a ESPACIOP
PSPACE-completo Igual que ESPACIOP-completo
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.
Obtenido de "Anexo:Clases de complejidad"

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Clases de complejidad P y NP — Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP completos en este caso fue determinada por Ladner.[1] La relación entre las clases de complejidad P …   Wikipedia Español

  • Jerarquía de clases de complejidad acotadas por espacio — En teoría de la complejidad computacional se utilizan diferentes clases de complejidad para catalogar familias de problemas de decisión en relación con la cantidad de espacio que utilizan para ser resueltos. Estas clases de complejidad pueden ser …   Wikipedia Español

  • 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 …   Wikipedia Español

  • Jerarquía de clases de complejidad acotadas por espacio — En teoría de la complejidad computacional se utilizan diferentes clases de complejidad para catalogar familias de problemas de decisión en base a la cantidad de espacio que utilizan para ser resueltos. Estas clases de complejidad pueden ser… …   Enciclopedia Universal

  • Lista de 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 …   Enciclopedia Universal

  • Complejidad computacional — Saltar a navegación, búsqueda La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema. Los recursos… …   Wikipedia Español

  • Complejidad — ► sustantivo femenino Cualidad de lo complejo o complicado: ■ a pesar de la complejidad del ejercicio, lo resolvió bien. TAMBIÉN complexidad ANTÓNIMO sencillez simplicidad * * * complejidad f. Cualidad de complejo. ⇒ *Complicar. * * * complejidad …   Enciclopedia Universal

  • Teoría de la complejidad computacional — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • NP (Complejidad computacional) — Saltar a navegación, búsqueda Los recursos comúnmente estudiados en complejidad computacional son: – El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema. – El espacio: mediante… …   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

Compartir el artículo y extractos

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