Classe de complexidade

Muitas importantes classes de complexidade podem ser definidas por delimitação de tempo ou espaço usando um algoritmo. Algumas importantes classes de problemas de decisão definidas desta maneiras são as seguintes: Ocorre que PSPACE = NPSPACE e EXPSPACE = NEXPSPACE pelo Teorema de Savitch. Outra importante classe de complexidade inclui BPP, ZPP e RP, as quais são definidas pela Máquina de Turing Probabilística. AC e NC, as quais são definidas usando circuitos booleanos. BQP e QMA, as quais são definidas usando Máquina de Turing Quântica. #P é uma importante classe de complexidade de problemas de contagem (problemas não decidíveis). Classes como IP e AM são definidas usando Sistemas de Provas Interativas. ALL é a classe de todos os problemas de decisão.

Muitas classes de complexidade são definidas usando o conceito de redução. Uma redução é uma transformação de um problema em outro problema. Ele captura a noção informal de um problema ser menos difícil que um outro problema. Por exemplo, se um problema X pode ser resolvido usando um algoritmo para resolver Y, X não é mais difícil que Y, e nós podemos dizer que X se reduz a Y. Existem vários tipos diferentes de reduções, baseados nos métodos de redução, tais como as reduções de Cook, Karp e Levin, e o limite da complexidade das reduções, tais quais a redução em tempo polinomial ou na redução em espaço logarítmico. A redução mais comum usada é a redução por tempo polinomial. Isso significa que o processo de redução leva um tempo polinomial para ser realizado. Por exemplo, o problema de elevar um inteiro ao quadrado pode ser reduzido ao problema de multiplicar dois inteiros. Ou seja, um algoritmo para multiplicar dois integrais pode ser usado para elevar um inteiro ao quadrado. De fato isto pode ser feito dando a mesma entrada para as duas entradas do algoritmo de multiplicação. Assim, nós vemos que potenciação não é mais difícil que multiplicação, desde que potenciação pode ser reduzido à multiplicação.

Classes de complexidade tem um variedade de propriedades de fechamento; por exemplo, classes decidíveis podem ser fechadas sob negação, disjunção, conjunção, ou mesmo sob todas as operações booleanas. Além disso, elas podem ser fechadas sob uma variedade de esquemas de quantificação. P, por exemplo, é fechada sob todas as operações booleanas, e sob quantificações sobre domínios de tamanho polinomial. Contudo, é mais provável que não seja fechado sob quantificações sobre domínios de tamanho exponencial. Cada classe X a qual não é fechada sob negação tem uma classe complemento Co-Y, que consiste dos complementos das linguagens contidas em X. Semelhantemente pode-se definir um fechamento booleano de uma classe, e assim por diante, isto é não é muito comum ser feito. Um possível caminho para separar duas classes de complexidades é encontrar alguma propriedade de fechamento que um possui e o outro não.

A seguinte tabela mostra algumas classes de problemas (ou linguagens, ou gramáticas) que são consideradas na teoria da complexidade. Se a classe X é um subconjunto restrito de Y, então X é mostrado abaixo de Y, com uma linha escura conectando-os. Se X é um subconjunto, mas não se sabe se os conjuntos são iguais, então a linha é tracejada. Tecnicamente a separação entre decidível e não decidível pertence mais ao estudo da teoria da complexidade mas é útil colocar as classes de complexidade em perspectiva.