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 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.
| #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 respuesta probablemente correcta) |
| 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 |
| DSPACE(f(n)) | Resolubles con una máquina determinista en espacio O(f(n)). |
| 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 |
| ESPACIO | Resoluble en espacio exponencial con exponente lineal |
| EXP | Igual que EXPTIME |
| EXPSPACE | Resoluble en espacio exponencial |
| EXPTIME | Resoluble en tiempo exponencial |
| FNP | Análoga a NP para problemas funcionales |
| FP | Análoga de P para problemas funcionales |
| FPNP | Análoga de 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 |
| NESPACE | Resoluble en espacio exponencial con exponente lineal por una máquina no-determinista |
| NEXP | Igual a NEXPTIME |
| NEXPSPACE | Resoluble por una máquina no-determinista en espacio exponencial |
| 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 | NP-completo o más difícil |
| NSPACE(f(n)) | Resoluble por una máquina no-determinista en espacio O(f(n)). |
| 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 ½) |
| PSPACE | Resoluble en espacio polinómico y tiempo ilimitado |
| PSPACE-completo | Los problemas más difíciles de PSPACE |
| RP | Resoluble en tiempo polinómico con un algoritmo aleatorio (respuesta negativa probablemente correcta, respuesta positiva exacta) |
| UP | Funciones polinómicas no-deterministas no ambiguas. |
| ZPP | Resoluble por algoritmos aleatorios (respuesta siempre correcta, tiempo no acotado, en promedio polinómico) |
Enlaces externos
- [1] - Wiki que lista unas 400 clases de complejidad y sus propiedades.
Categorías
Clases de complejidad | Listas