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
[editar]| #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 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
[editar]| 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
[editar]- ↑ 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
[editar]- qwiki.caltech.edu - Wiki que lista unas 400 clases de complejidad y sus propiedades.
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Credit:
(see original file).
