Classe de complexidade

Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas relacionados aos recursos computacionais baseados em complexidade. Uma típica classe de complexidade é definida da seguinte forma:

O conjunto de problemas que podem ser resolvidos por uma máquina abstrata M usando O(f(n)) de recurso R, onde n é o tamanho da entrada.

Por exemplo, a classe NP é o conjunto de problemas decidíveis que podem ser resolvidos por uma Máquina de Turing Não-Determinística em tempo polinomial, onde a classe PSPACE é o conjunto de problemas decidíveis que podem ser resolvidos por uma Máquina de Turing Determinística em espaço polinomial.

As mais simples classes de complexidade são definidas pelos seguintes fatores:

O tipo de problema computacional: os mais comumentes usados são o problemas de decisão. Contudo, classes de complexidade podem ser definidas baseadas nos problemas funcionais (Um exemplo é o conjunto FP), problemas de contagem (Ex. #P), problemas de otimização, problemas de promessa, etc.

O modelo de computação: o modelo de computação mais comum é a Máquina de Turing Determinística, porém, muitas classes de complexidade são baseadas em Máquinas de Turing Não-Determiníticas, circuitos booleanos, Máquina de Turing Quântica, circuitos monótonos, etc.

O(s) recurso(s) que está(ão) sendo limitado(os) e os limites: Estas duas propriedades são usualmente declaradas juntas, assim como "tempo polinomial", "espaço logarítmico", "constante de profundidade", etc.

Muitas classes de complexidade podem ser caracterizadas em termos da matemática lógica, necessária para expressá-las.

Delimitar o tempo computacional por cima por alguma função concreta f(n) muitas vezes produz classes de complexidade que dependem da escolha do modelo da máquina. Por exemplo, a linguagem {xx| x é uma cadeia binária} pode ser decidida em tempo linear numa Máquina de Turing Multi-Fita, mas necessariamente requer um tempo exponencial no modelo da Máquina de Turing de fita simples. Se nós permitirmos um variação polinomial em tempo de execução, a tese de Cobham-Edmonds afirma que, "as complexidades de tempo em dois modelos razoáveis e gerais são polinomialmente relacionados" (Goldreich 2008, Capítulo 1.2). Esti forma a base da classe de complexidade P, a qual é o conjunto de problemas resolvidos por uma Máquina de Turing Determinística dentro de um tempo polinomial. O conjunto correspondente de problemas funcionais para P é FP.

Os axiomas de Blum podem ser usados para definir classes de complexidade sem se referir a um modelo computacional concreto.

Importantes classes 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:

Classes de Complexidade	Modelo de Computação	Restrição de Recurso
DTIME(f(n))	Máquina de Turing Determinística	Tempo f(n)
P	Máquina de Turing Determinística	Tempo polinomial(n)
EXPTIME	Máquina de Turing Determinística	Time 2^{polinomial(n)}
NTIME(f(n))	Máquina de Turing Não-Determinística	Tempo f(n)
NP	Máquina de Turing Não-Determinística	Tempo polinomial(n)
NEXPTIME	Máquina de Turing Não-Determinística	Tempo 2^{polinomial(n)}
DSPACE(f(n))	Máquina de Turing Determinística	Espaço f(n)
L	Máquina de Turing Determinística	Espaço O(log n)
PSPACE	Máquina de Turing Determinística	Espaço polinomial(n)
EXPSPACE	Máquina de Turing Determinística	Espaço 2^{polinomial(n)}
NSPACE(f(n))	Máquina de Turing Não-Determinística	Espaço f(n)
NL	Máquina de Turing Não-Determinística	Espaço O(log n)
NPSPACE	Máquina de Turing Não-Determinística	Espaço polinomial(n)
NEXPSPACE	Máquina de Turing Não-Determinística	Espaço 2^{polinomial(n)}

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.

Redução

Artigo Principal: Redução (complexidade)

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.

Isso motiva o conceito de um problema ser mais difícil que a classe de complexidade. O problema X é difícil para uma classe de problemas C se todo problema em C pode ser reduzido a X. Assim nenhum problema é mais difícil que X, desde que o algoritmo para resolver X nos permita resolver qualquer problema de C. Claro, a noção de problemas difíceis depende do tipo de redução que está sendo usada. Para as classes de complexidade maiores que P, reduções em tempo polinomial são comumente usadas. Em particular, o conjunto de problemas que são difíceis para NP fazem parte do conjunto de problemas NP Difíceis.

Se um problema X está em C e é difícil para C, então X é dito completo para C. Isso significa que X é o problema mais difícil em C (Desde que poderia haver muitos problemas os quais são igualmente difíceis, pode-se dizer que X é um dos problemas mais difíceis em C). Sendo assim, a classe dos problemas NP-Completos contém os problemas mais difíceis em NP, no sentido de que eles são os mais propensos a não estar em P. Por causa do problema P = NP, que não foi resolvido, ser capaz de reduzir outro problema, Π₁, para um problema NP-Completo, Π₂, indicaria que existe uma solução em tempo polinomial conhecida para Π₁. Isto é porque uma solução em tempo polinomial para Π₁ produziria uma solução polinomial para Π₂. Semelhantemente, porque todos os problemas NP podem ser reduzidos para o conjunto, encontrando um problema NP-Completo que pode ser resolvido em tempo polinomial significaria que P = NP.

Problema do fechamento de classes

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.

Relacionamento entre classes de complexidade

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.

Problema da Decisão

Tipo 0 (Recurssivamente Enumerável)

Indecidível

Decidível

EXPSPACE

NEXPTIME

EXPTIME

PSPACE

Tipo 1 (Gramática Sensível ao Contexto)

Co-NP

BQP

NP

BPP

P

NC

Tipo 2 (Gramática Livre de Contexto)

Tipo 3 (Gramática Regular)

Hierarquia de teoremas

Para as classes de complexidade definidas deste modo, é desejável provar que relaxando os requisitos em tempo de computação de fato define um conjunto maior de problemas. Em particular, embora DTIME(n) esteja contido em DTIME(n²), seria interessante saber se a inclusão é restrita. Para requisitos de tempo e espaço, a resposta para essas questões é dada por hierarquia de tempo e espaço, respectivamente. Eles são chamados de hierarquia de teoremas porque eles induzem uma hierarquia adequada nas classes definidas construindo os respectivos recursos. Assim, existe pares de classes de complexidade tais que uma é apropriadamente incluída na outra. Tendo deduzido as inclusões adequadas, nós podemos prosseguir para fazer declarações quantitativas sobre quanto espaço ou tempo adicional é necessário em ordem para aumentar o número de problemas que podem se resolvidos.

Mais precisamente, o Teorema da hierarquia de tempo diz:

\operatorname {DTIME} {\big (}f(n){\big )}\subsetneq \operatorname {DTIME} {\big (}f(n)\cdot \log ^{2}(f(n)){\big )}

.

O Teorema da hierarquia de espaço diz:

\operatorname {DSPACE} {\big (}f(n){\big )}\subsetneq \operatorname {DSPACE} {\big (}f(n)\cdot \log(f(n)){\big )}

.

O teorema da hierarquia de espaço e tempo formar a base para resultado de mais separações de classes de complexidade. Por exemplo, o teorema da hierarquia de tempo nos diz que P está restritamente contido em EXPTIME, e o teorema da hierarquia de espaço nos diz que L está estritamente contido em PSPACE.

Ver também

Lista de classes de complexidade

Leitura adicional

The Complexity Zoo: Uma larga lista de classes, para experts.
Diagram by Neil Immerman Mostrando a hierarquia de classes de complexidade e como elas se encaixam
Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. Referência sobre problemas NP-completos - uma importante categoria de problemas cujas soluções parecem exigir um tempo impraticavelmente longo para calcular.