Lista de classes de complexidade

Essa é uma lista de classes de complexidade da teoria da complexidade computacional. Para outros assuntos sobre computabilidade e complexidade, veja list of computability and complexity topics.

Muitas dessas classes tem uma outra classe com prefixo 'co' que corresponde ao complemento de todas as linguagens da classe original. Por exemplo, se uma linguagem L está em NP então o complemento de L está em co-NP (isso não significa que o complemento de NP é co-NP - exitem linguagens que são conhecidas por estarem nas duas classes, e outras que são conhecidas por não estarem em nenhuma delas).

"Os problemas mais difíceis" de uma classe referem-se aos problemas que pertencem a classe e todos os outros problemas dessa classe podem ser reduzidos a ele, além disso, a redução é também um problema da classe determinada ou de seu subconjunto.

#P Contagem de soluções para um problema NP.
#P-complete Os problemas mais difíceis em #P.
2-EXPTIME Solúveis em tempo duplamente exponencial.
AC0 Uma classe de complexidade de circuito de profundidade limitada.
ACC0 Uma classe de complexidade de circuito de profundidade limitada e contagem de portas.
AC Uma classe de complexidade de circuito.
AH A hierarquia aritmética.
AP A classe de problemas que uma máquina de Turing alternada pode resolver em tempo polinomial.
APX Problemas de otimização que possuem algoritmos de aproximação com um rácio de aproximação constante.
AM Solúveis em tempo polinomial por um protocolo Arthut-Merlin.
BPP Solúveis em tempo polinomial por algoritmos randomizados (a resposta provavelmente é correta).
BQP Solúveis em tempo polinomial por um computador quântico (a resposta provavelmente é correta).
co-NP Respostas "Não" verificáveis em tempo polinomial por uma máquina de Turing não determinística.
co-NP-complete Os problemas mais difíceis em co-NP.
DSPACE(f(n)) Solúveis por uma máquina de Turing determinística com espaço O(f(n)).
DTIME(f(n)) Solúveis por uma máquina de Turing determinística em tempo O(f(n)).
E Solúveis em tempo exponencial com expoente linear.
ELEMENTARY A união das classes na hierarquia exponencial.
ESPACE Solúvel com espaço exponencial com expoente linear.
EXP O mesmo que EXPTIME.
EXPSPACE Solúvel com espaço exponencial.
EXPTIME Solúvel em tmepo exponencial.
FNP O análogo à NP para problemas de função.
FP O análogo à P para problemas de função.
FP^NP O análogo à P^NP para problemas de função; A origem do problema do caixeiro viajante.
FPT Parâmetro fixo tratável.
GapL Redutível em espaço logarítmico para computar o determinante inteiro de uma matriz.
IP Solúvel em tempo polinomial por um sistema de prova interativo.
L Solúvel com um espaço logarítmico (pequeno).
LOGCFL Redutível em espaço logarítmico para uma linguagem livre do contexto.
MA Solúvel em tempo polinomial por um protocolo Merlin-Arthur.
NC Solúvel eficientemente (em tempo polylog) em computação paralela.
NE Solúvel por uma máquina de Turing não determinística em tempo exponencial com expoente linear.
NESPACE Solúvel por uma máquina de Turing não determinística com espaço exponencial com expoente linear.
NEXP O mesmo que NEXPTIME.
NEXPSPACE Solúvel por uma máquina de Turing não determinística com espaço exponencial.
NEXPTIME Solúvel por uma máquina de Turing não determinística em tempo exponencial.
NL Respostas "Sim" verificáveis com espaço logarítmico.
NONELEMENTARY Complemento de ELEMENTARY.
NP Respostas "Sim" verificáveis em tempo polinomial.
NP-complete Os problemas mais difíceis ou mais caros em NP.
NP-easy O análogo à P^NP para problemas de função; outro nome para FP^NP.
NP-equivalent Os problemas mais difíceis em FP^NP.
NP-hard Pelo menos tão difícil quanto todos os problemas em NP, mas não conhecido por ser da mesma classe de complexidade.
NSPACE(f(n)) Solúvel por uma máquina de Turing não determinística com espaço O(f(n)).
NTIME(f(n)) Solúvel por uma máquina de Turing não determinística em temo O(f(n)).
P Solúveis em tempo polinomial.
P-complete Os problemas mais difíceis em P para resolver em computadores paralelos.
P/poly Solúvel em tempo polinomial dado uma "dica" dependendo apenas do tamanho da entrada.
PCP Prova probabilisticamente verificável.
PH A união das classes na hierarquia polinomial.
P^NP Solúvel em tempo polinomial com um oráculo para um problema em NP; também conhecido como Δ₂P.
PP Probabilisticamente polinomial (resposta está correta com probabilidade ligeiramente superior a 1/2).
PR Solúvel por recursividade desenvolvendo funções aritméticas.
PSPACE Solúvel com espaço polinomial.
PSPACE-complete Os problemas mais difíceis em PSPACE.
R Solúvel me uma quantidade finita de tempo.
RE Problemas a que podemos responder "Sim" em uma quantidade finita de tempo, mas um "Não" como resposta pode nunca vir.
RL Solúvel com espaço logarítmico por algoritmos randomizados (respostas "Não" são provavelmente corretas, respostas "Sim" certamente são corretas).
RP Solúvel em tempo logarítmico por algoritmos randomizados (respostas "Não" são provavelmente corretas, respostas "Sim" certamente são corretas).
SL Problemas log-space redutíveis a determinar se existe um caminho entre dados vértices em um grafo não direcionado. Em outubro de 2004 descobriu-se que esta classe é, de fato, igual a L.
S₂P Jogos de uma rodada com movimentos simultâneos arbitrados deterministicamente em tempo polinomial.
TFNP Total de problemas de função que podem ser resolvidos em tempo polinomial não determinístico. Um problema nesta classe tem a propriedade de que cada entrada tem uma saída cuja validade pode ser verificada de forma eficiente, e o desafio computacional é encontrar uma saída válida.
UP Funções inequívocas não determinísticas de tempo polinomial.
ZPL Solúvel por algoritmos randomizados (a resposta é sempre correta, o uso médio do espaço é logarítmico).
ZPP Solúvel por algoritmos randomizados (a resposta é sempre correta, o tempo médio de execução é polinomial).

Referências

^ Sanjeev Arora, Boaz Barak (2009), Computational Complexity: A Modern Approach, Cambridge University Press; 1 edition, ISBN 978-0-521-42426-4
^ "S₂P: Second Level of the Symmetric Hierarchy". Stanford University Complexity Zoo.

Ligações externos

Complexity Zoo - list of over 400 complexity classes and their properties