Teoria da complexidade computacional

Em ciência da computação teórica e matemática, a teoria da complexidade computacional concentra-se em classificar problemas computacionais de acordo com o uso de recursos e explora as relações entre essas classificações. Um problema computacional é uma tarefa resolvida por um computador e solucionável pela aplicação mecânica de etapas matemáticas, como um algoritmo.

Um problema é considerado intrinsecamente difícil se sua solução exigir recursos significativos, independentemente do algoritmo usado. A teoria formaliza essa intuição, introduzindo modelos matemáticos de computação para estudar esses problemas e quantificando sua complexidade computacional, ou seja, a quantidade de recursos necessários para resolvê-los, como tempo e armazenamento.

Outras medidas de complexidade também são usadas, como a quantidade de comunicação (usada na complexidade de comunicação), o número de portas em um circuito (usado na complexidade de circuitos) e o número de processadores (usado na computação paralela). Um dos papéis da teoria da complexidade computacional é determinar os limites práticos do que os computadores podem e não podem fazer. O problema P versus NP, um dos sete Problemas do Prêmio Millennium, faz parte do campo da complexidade computacional.

Áreas intimamente relacionadas na ciência da computação teórica são a análise de algoritmos e a teoria da computabilidade. Uma diferença fundamental entre a análise de algoritmos e a teoria da complexidade computacional é que a primeira dedica-se a analisar a quantidade de recursos necessários para um algoritmo específico resolver um problema, enquanto a segunda faz uma pergunta mais geral sobre todos os algoritmos possíveis que poderiam ser usados para resolver o mesmo problema. Mais precisamente, a teoria da complexidade computacional tenta classificar problemas que podem ou não ser resolvidos com recursos apropriadamente restritos. Por sua vez, impor restrições aos recursos disponíveis é o que distingue a complexidade computacional da teoria da computabilidade: esta última teoria pergunta que tipos de problemas podem, em princípio, ser resolvidos algoritmicamente.

Problemas computacionais

Um passeio do caixeiro viajante por 14 cidades alemãs

Instâncias de problema

Um problema computacional pode ser visto como uma coleção infinita de instâncias juntamente com um conjunto (possivelmente vazio) de soluções para cada instância. A cadeia de caracteres de entrada para um problema computacional é chamada de instância do problema e não deve ser confundida com o problema em si. Na teoria da complexidade computacional, um problema refere-se à questão abstrata a ser resolvida. Em contraste, uma instância desse problema é um enunciado bastante concreto, que pode servir como entrada para um problema de decisão. Por exemplo, considere o problema de teste de primalidade. A instância é um número (por exemplo, 15) e a solução é "sim" se o número for primo e "não" caso contrário (neste caso, 15 não é primo e a resposta é "não"). Dito de outra forma, a instância é uma entrada particular para o problema, e a solução é a saída correspondente à entrada fornecida.

Para destacar ainda mais a diferença entre um problema e uma instância, considere a seguinte instância da versão de decisão do problema do caixeiro viajante: Existe uma rota de no máximo 2000 quilômetros passando por todas as 14 maiores cidades da Alemanha? A resposta quantitativa para esta instância particular do problema é de pouca utilidade para resolver outras instâncias do problema, como perguntar por um passeio de ida e volta por 14 locais em Milão cujo comprimento total seja no máximo 10 km. Por essa razão, a teoria da complexidade trata de problemas computacionais e não de instâncias particulares de problemas.

Representação de instâncias de problema

Ao considerar problemas computacionais, uma instância de problema é uma cadeia de caracteres sobre um alfabeto. Normalmente, o alfabeto é considerado o alfabeto binário (ou seja, o conjunto {0,1}), e assim as cadeias são cadeias de bits. Como em um computador real, objetos matemáticos diferentes de cadeias de bits devem ser adequadamente codificados. Por exemplo, inteiros podem ser representados em notação binária, e grafos podem ser codificados diretamente através de suas matrizes de adjacência, ou codificando suas listas de adjacência em binário.

Embora algumas provas de teoremas da teoria da complexidade assumam regularmente alguma escolha concreta de codificação de entrada, tenta-se manter a discussão suficientemente abstrata para ser independente da escolha precisa da codificação. Isso pode ser alcançado garantindo que diferentes representações possam ser transformadas umas nas outras de forma eficiente.

Problemas de decisão como linguagens formais

Um problema de decisão tem apenas duas saídas possíveis, sim ou não (ou alternadamente 1 ou 0) para qualquer entrada.

Problemas de decisão são um dos objetos centrais de estudo na teoria da complexidade computacional. Um problema de decisão é um tipo de problema computacional onde a resposta é sim ou não (alternativamente, 1 ou 0). Um problema de decisão pode ser visto como uma linguagem formal, onde os membros da linguagem são instâncias cuja saída é sim, e os não-membros são aquelas instâncias cuja saída é não. O objetivo é decidir, com o auxílio de um algoritmo, se uma dada cadeia de entrada é um membro da linguagem formal em consideração. Se o algoritmo que decide este problema retornar a resposta sim, diz-se que o algoritmo aceita a cadeia de entrada; caso contrário, diz-se que rejeita a entrada.

Um exemplo de problema de decisão é o seguinte. A entrada é um grafo arbitrário. O problema consiste em decidir se o grafo dado é conexo ou não. A linguagem formal associada a este problema de decisão é então o conjunto de todos os grafos conexos — para obter uma definição precisa desta linguagem, é preciso decidir como os grafos são codificados como cadeias binárias.

Problemas de função

Um problema de função é um problema computacional onde uma única saída (de uma função total) é esperada para cada entrada, mas a saída pode ser mais complexa do que a de um problema de decisão — ou seja, a saída não é apenas sim ou não. Exemplos notáveis incluem o problema do caixeiro viajante e o problema de fatoração de inteiros.

É tentador pensar que a noção de problemas de função é muito mais rica do que a noção de problemas de decisão. No entanto, este não é realmente o caso, pois problemas de função podem ser reformulados como problemas de decisão. Por exemplo, a multiplicação de dois inteiros pode ser expressa como o conjunto de triplas $(a,b,c)$ tais que a relação $a\times b=c$ é válida. Decidir se uma dada tripla é membro deste conjunto corresponde a resolver o problema de multiplicar dois números.

Medindo o tamanho de uma instância

Para medir a dificuldade de resolver um problema computacional, pode-se querer ver quanto tempo o melhor algoritmo requer para resolver o problema. No entanto, o tempo de execução pode, em geral, depender da instância. Em particular, instâncias maiores exigirão mais tempo para serem resolvidas. Assim, o tempo necessário para resolver um problema (ou o espaço necessário, ou qualquer medida de complexidade) é calculado como uma função do tamanho da instância. O tamanho da entrada é tipicamente medido em bits. A teoria da complexidade estuda como os algoritmos escalam à medida que o tamanho da entrada aumenta. Por exemplo, no problema de determinar se um grafo é conexo, quanto tempo a mais leva para resolver um problema para um grafo com $2n$ vértices em comparação com o tempo gasto para um grafo com $n$ vértices?

Se o tamanho da entrada é $n$, o tempo gasto pode ser expresso como uma função de $n$. Como o tempo gasto em diferentes entradas do mesmo tamanho pode ser diferente, a complexidade de tempo de pior caso $T(n)$ é definida como o tempo máximo gasto em todas as entradas de tamanho $n$. Se $T(n)$ é um polinômio em $n$, então o algoritmo é dito um algoritmo de tempo polinomial. A tese de Cobham argumenta que um problema pode ser resolvido com uma quantidade viável de recursos se e somente se ele admite um algoritmo de tempo polinomial.

Modelos de máquina e medidas de complexidade

Máquina de Turing

Ver artigo principal: Máquina de Turing

Uma ilustração de uma máquina de Turing

Uma máquina de Turing é um modelo matemático de uma máquina de computação geral. É um dispositivo teórico que manipula símbolos contidos em uma fita. As máquinas de Turing não se destinam a ser uma tecnologia de computação prática, mas sim um modelo geral de uma máquina de computação — qualquer coisa, desde um supercomputador avançado a um matemático com lápis e papel. Acredita-se que se um problema pode ser resolvido por um algoritmo, existe uma máquina de Turing que resolve o problema. De fato, esta é a afirmação da tese de Church-Turing. Além disso, sabe-se que tudo o que pode ser computado em outros modelos de computação conhecidos hoje, como uma máquina RAM, Jogo da Vida de Conway, autômato celular, cálculo lambda ou qualquer linguagem de programação, pode ser computado em uma máquina de Turing. Como as máquinas de Turing são fáceis de analisar matematicamente e acredita-se que sejam tão poderosas quanto qualquer outro modelo de computação, a máquina de Turing é o modelo mais comumente usado na teoria da complexidade.

Muitos tipos de máquinas de Turing são usados para definir classes de complexidade, como máquinas de Turing determinísticas, máquinas de Turing probabilísticas, máquinas de Turing não determinísticas, máquinas de Turing quânticas, máquinas de Turing simétricas e máquinas de Turing alternadas. Todas são igualmente poderosas em princípio, mas quando os recursos (como tempo ou espaço) são limitados, algumas delas podem ser mais poderosas do que outras.

Uma máquina de Turing determinística é a máquina de Turing mais básica, que usa um conjunto fixo de regras para determinar suas ações futuras. Uma máquina de Turing probabilística é uma máquina de Turing determinística com um suprimento extra de bits aleatórios. A capacidade de tomar decisões probabilísticas frequentemente ajuda algoritmos a resolver problemas de forma mais eficiente. Algoritmos que usam bits aleatórios são chamados de algoritmos randomizados. Uma máquina de Turing não determinística é uma máquina de Turing determinística com um recurso adicional de não determinismo, que permite a uma máquina de Turing ter múltiplas ações futuras possíveis a partir de um determinado estado. Uma maneira de ver o não determinismo é que a máquina de Turing se ramifica em muitos caminhos computacionais possíveis a cada passo, e se ela resolver o problema em qualquer um desses ramos, diz-se que resolveu o problema. Claramente, este modelo não pretende ser um modelo fisicamente realizável, é apenas uma máquina abstrata teoricamente interessante que dá origem a classes de complexidade particularmente interessantes. Para exemplos, veja algoritmo não determinístico.

Outros modelos de máquina

Muitos modelos de máquina diferentes das máquinas de Turing com múltiplas fitas padrão foram propostos na literatura, por exemplo, máquinas de acesso aleatório. Surpreendentemente, cada um desses modelos pode ser convertido em outro sem fornecer poder computacional extra. O tempo e o consumo de memória desses modelos alternativos podem variar. O que todos esses modelos têm em comum é que as máquinas operam de forma determinística.

No entanto, alguns problemas computacionais são mais fáceis de analisar em termos de recursos mais incomuns. Por exemplo, uma máquina de Turing não determinística é um modelo computacional que pode se ramificar para verificar muitas possibilidades diferentes ao mesmo tempo. A máquina de Turing não determinística tem muito pouco a ver com a forma como fisicamente queremos computar algoritmos, mas sua ramificação captura exatamente muitos dos modelos matemáticos que queremos analisar, de modo que o tempo não determinístico é um recurso muito importante na análise de problemas computacionais.

Medidas de complexidade

Para uma definição precisa do que significa resolver um problema usando uma determinada quantidade de tempo e espaço, um modelo computacional como a máquina de Turing determinística é usado. O tempo requerido por uma máquina de Turing determinística $M$ na entrada $x$ é o número total de transições de estado, ou passos, que a máquina faz antes de parar e produzir a resposta ("sim" ou "não"). Diz-se que uma máquina de Turing $M$ opera dentro do tempo $f(n)$ se o tempo requerido por $M$ em cada entrada de comprimento $n$ é no máximo $f(n)$. Um problema de decisão $A$ pode ser resolvido em tempo $f(n)$ se existe uma máquina de Turing operando em tempo $f(n)$ que resolve o problema. Como a teoria da complexidade está interessada em classificar problemas com base em sua dificuldade, definem-se conjuntos de problemas baseados em alguns critérios. Por exemplo, o conjunto de problemas solucionáveis dentro do tempo $f(n)$ em uma máquina de Turing determinística é então denotado por DTIME($f(n)$).

Definições análogas podem ser feitas para requisitos de espaço. Embora tempo e espaço sejam os recursos de complexidade mais conhecidos, qualquer medida de complexidade pode ser vista como um recurso computacional. As medidas de complexidade são muito geralmente definidas pelos axiomas de Blum. Outras medidas de complexidade usadas na teoria da complexidade incluem complexidade de comunicação, complexidade de circuitos e complexidade de árvore de decisão.

A complexidade de um algoritmo é frequentemente expressa usando notação O grande.

Complexidade de melhor, pior e caso médio

Visualização do algoritmo quicksort, que tem desempenho de caso médio ${\mathcal {O}}(n\log n)$

A complexidade de melhor, pior e caso médio refere-se a três maneiras diferentes de medir a complexidade de tempo (ou qualquer outra medida de complexidade) de diferentes entradas do mesmo tamanho. Como algumas entradas de tamanho $n$ podem ser mais rápidas de resolver do que outras, definimos as seguintes complexidades:

1. Complexidade de melhor caso: Esta é a complexidade de resolver o problema para a melhor entrada de tamanho $n$.
2. Complexidade de caso médio: Esta é a complexidade de resolver o problema em média, para entradas de tamanho n. Esta complexidade é definida apenas com respeito a uma distribuição de probabilidade sobre as entradas. Por exemplo, se todas as entradas do mesmo tamanho são consideradas igualmente prováveis de aparecer, a complexidade de caso médio pode ser definida com respeito à distribuição uniforme sobre todas as entradas de tamanho $n$.
3. Análise amortizada: A análise amortizada considera tanto as operações caras quanto as menos caras em conjunto ao longo de toda a série de operações do algoritmo.
4. Complexidade de pior caso: Esta é a complexidade de resolver o problema para a pior entrada de tamanho $n$.

A ordem do mais barato ao mais caro é: Melhor, médio (da distribuição uniforme discreta), amortizado, pior.

Por exemplo, o algoritmo de ordenação determinístico quicksort resolve o problema de ordenar uma lista de inteiros. O pior caso ocorre quando o pivô é sempre o maior ou o menor valor da lista (de modo que a lista nunca é dividida). Neste caso, o algoritmo leva tempo O($n^{2}$). Se assumirmos que todas as permutações possíveis da lista de entrada são igualmente prováveis, o tempo médio gasto para ordenar é $O(n\log n)$. O melhor caso ocorre quando cada pivoteamento divide a lista ao meio, também necessitando de tempo $O(n\log n)$.

Limites superior e inferior na complexidade de problemas

Para classificar o tempo de computação (ou recursos similares, como consumo de espaço), é útil demonstrar limites superiores e inferiores na quantidade máxima de tempo exigida pelo algoritmo mais eficiente para resolver um determinado problema. A complexidade de um algoritmo é geralmente considerada como sua complexidade de pior caso, salvo especificação em contrário. Analisar um algoritmo particular está dentro do campo da análise de algoritmos. Para mostrar um limite superior $T(n)$ na complexidade de tempo de um problema, é necessário apenas mostrar que existe um algoritmo particular com tempo de execução no máximo $T(n)$. No entanto, provar limites inferiores é muito mais difícil, pois limites inferiores fazem uma afirmação sobre todos os algoritmos possíveis que resolvem um determinado problema. A frase "todos os algoritmos possíveis" inclui não apenas os algoritmos conhecidos hoje, mas qualquer algoritmo que possa ser descoberto no futuro. Mostrar um limite inferior de $T(n)$ para um problema requer mostrar que nenhum algoritmo pode ter complexidade de tempo inferior a $T(n)$.

Limites superiores e inferiores são geralmente declarados usando a notação O grande, que oculta fatores constantes e termos menores. Isso torna os limites independentes dos detalhes específicos do modelo computacional usado. Por exemplo, se $T(n)=7n^{2}+15n+40$, na notação O grande escreveríamos $T(n)\in O(n^{2})$.

Classes de complexidade

Ver artigo principal: Classe de complexidade

Definindo classes de complexidade

Uma classe de complexidade é um conjunto de problemas de complexidade relacionada. Classes de complexidade mais simples são definidas pelos seguintes fatores:

• O tipo de problema computacional: Os problemas mais comumente usados são os problemas de decisão. No entanto, classes de complexidade podem ser definidas com base em problemas de função, problemas de contagem, 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, mas muitas classes de complexidade são baseadas em máquinas de Turing não determinísticas, circuitos booleanos, máquinas de Turing quânticas, circuitos monótonos, etc.
• O recurso (ou recursos) que está sendo limitado e o limite: Essas duas propriedades são geralmente declaradas juntas, como "tempo polinomial", "espaço logarítmico", "profundidade constante", etc.

Algumas classes de complexidade têm definições complicadas que não se encaixam neste quadro. Assim, uma classe de complexidade típica tem uma definição como a seguinte:

O conjunto de problemas de decisão solucionáveis por uma máquina de Turing determinística dentro do tempo $f(n)$. (Esta classe de complexidade é conhecida como DTIME($f(n)$).)

Mas limitar o tempo de computação acima por alguma função concreta $f(n)$ frequentemente produz classes de complexidade que dependem do modelo de máquina escolhido. Por exemplo, a linguagem $\{xx\mid x{\text{ é qualquer cadeia binária}}\}$ pode ser resolvida em tempo linear em uma máquina de Turing com múltiplas fitas, mas necessariamente requer tempo quadrático no modelo de máquinas de Turing com fita única. Se permitirmos variações polinomiais no tempo de execução, a tese de Cobham-Edmonds afirma que "as complexidades de tempo em quaisquer dois modelos razoáveis e gerais de computação são polinomialmente relacionadas" (Goldreich 2008, Capítulo 1.2). Isso forma a base para a classe de complexidade P, que é o conjunto de problemas de decisão solucionáveis por uma máquina de Turing determinística em tempo polinomial. O conjunto correspondente de problemas de função é FP.

Classes de complexidade importantes

Uma representação da relação entre classes de complexidade; L seria outro passo "dentro" de NL

Muitas classes de complexidade importantes podem ser definidas limitando o tempo ou o espaço usado pelo algoritmo. Algumas classes de complexidade importantes de problemas de decisão definidas dessa maneira são as seguintes:

Recurso	Determinismo	Classe de complexidade	Restrição de recurso
Espaço	Não Determinístico	NSPACE($f(n)$)	$O(f(n))$
		NL	$O(\log n)$
		NPSPACE	$O({\text{poli}}(n))$
		NEXPSPACE	$O(2^{{\text{poli}}(n)})$
	Determinístico	DSPACE($f(n)$)	$O(f(n))$
		L	$O(\log n)$
		PSPACE	$O({\text{poli}}(n))$
		EXPSPACE	$O(2^{{\text{poli}}(n)})$
Tempo	Não Determinístico	NTIME($f(n)$)	$O(f(n))$
		NP	$O({\text{poli}}(n))$
		NEXPTIME	$O(2^{{\text{poli}}(n)})$
	Determinístico	DTIME($f(n)$)	$O(f(n))$
		P	$O({\text{poli}}(n))$
		EXPTIME	$O(2^{{\text{poli}}(n)})$

As classes de espaço logarítmico não consideram o espaço necessário para representar o problema.

Acontece que PSPACE = NPSPACE e EXPSPACE = NEXPSPACE pelo teorema de Savitch.

Outras classes de complexidade importantes incluem BPP, ZPP e RP, que são definidas usando máquinas de Turing probabilísticas; AC e NC, que são definidas usando circuitos booleanos; e BQP e QMA, que são definidas usando máquinas de Turing quânticas. #P é uma classe de complexidade importante de problemas de contagem (não problemas de decisão). Classes como IP e AM são definidas usando sistemas de prova interativos. ALL é a classe de todos os problemas de decisão.

Teoremas da hierarquia

Ver artigos principais: teorema da hierarquia de tempo e teorema da hierarquia de espaço

Para as classes de complexidade definidas dessa maneira, é desejável provar que relaxar os requisitos de (digamos) tempo de computação define de fato um conjunto maior de problemas. Em particular, embora DTIME($n$) esteja contido em DTIME($n^{2}$), seria interessante saber se a inclusão é estrita. Para requisitos de tempo e espaço, a resposta a tais questões é dada pelos teoremas da hierarquia de tempo e espaço, respectivamente. Eles são chamados de teoremas da hierarquia porque induzem uma hierarquia própria nas classes definidas pela restrição dos respectivos recursos. Assim, existem pares de classes de complexidade tais que uma está propriamente incluída na outra. Tendo deduzido tais inclusões próprias de conjuntos, podemos prosseguir para fazer afirmações quantitativas sobre quanto mais tempo ou espaço adicional é necessário para aumentar o número de problemas que podem ser resolvidos.

Mais precisamente, o teorema da hierarquia de tempo afirma que ${\mathsf {DTIME}}{\big (}o(f(n)){\big )}\subsetneq {\mathsf {DTIME}}{\big (}f(n)\cdot \log(f(n)){\big )}$.

O teorema da hierarquia de espaço afirma que ${\mathsf {DSPACE}}{\big (}o(f(n)){\big )}\subsetneq {\mathsf {DSPACE}}{\big (}f(n){\big )}$.

Os teoremas da hierarquia de tempo e espaço formam a base para a maioria dos resultados de separação de classes de complexidade. Por exemplo, o teorema da hierarquia de tempo nos diz que P está estritamente contido em EXPTIME, e o teorema da hierarquia de espaço nos diz que L está estritamente contido em PSPACE.

Redução

Ver 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. Ela captura a noção informal de um problema ser no máximo tão difícil quanto outro problema. Por exemplo, se um problema $X$ pode ser resolvido usando um algoritmo para $Y$, $X$ não é mais difícil do que $Y$, e dizemos que $X$ se reduz a $Y$. Existem muitos tipos diferentes de reduções, baseados no método de redução, como reduções de Cook, reduções de Karp e reduções de Levin, e no limite da complexidade das reduções, como reduções em tempo polinomial ou reduções em espaço logarítmico.

A redução mais comumente usada é a redução em tempo polinomial. Isso significa que o processo de redução leva tempo polinomial. Por exemplo, o problema de elevar ao quadrado um inteiro pode ser reduzido ao problema de multiplicar dois inteiros. Isso significa que um algoritmo para multiplicar dois inteiros pode ser usado para elevar ao quadrado um inteiro. De fato, isso pode ser feito dando a mesma entrada para ambas as entradas do algoritmo de multiplicação. Assim, vemos que elevar ao quadrado não é mais difícil do que a multiplicação, pois elevar ao quadrado pode ser reduzido à multiplicação.

Isso motiva o conceito de um problema ser difícil para uma classe de complexidade. Um problema $X$ é difícil para uma classe de problemas $C$ se todo problema em $C$ pode ser reduzido a $X$. Assim, nenhum problema em $C$ é mais difícil do que $X$, pois um algoritmo para $X$ nos permite resolver qualquer problema em $C$. A noção de problemas difíceis depende do tipo de redução usada. Para 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 é o 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$. (Como muitos problemas podem ser igualmente difíceis, pode-se dizer que $X$ é um dos problemas mais difíceis em $C$.) Assim, a classe de problemas NP-completos contém os problemas mais difíceis em NP, no sentido de que são aqueles mais provavelmente não estar em P. Como o problema P = NP não está resolvido, ser capaz de reduzir um problema NP-completo conhecido, $\Pi _{2}$, a outro problema, $\Pi _{1}$, indicaria que não há solução de tempo polinomial conhecida para $\Pi _{1}$. Isso porque uma solução de tempo polinomial para $\Pi _{1}$ produziria uma solução de tempo polinomial para $\Pi _{2}$. Similarmente, como todos os problemas NP podem ser reduzidos ao conjunto, encontrar um problema NP-completo que pode ser resolvido em tempo polinomial significaria que P = NP.

Problemas em aberto importantes

Diagrama de classes de complexidade assumindo que P ≠ NP. A existência de problemas em NP fora de P e de NP-completo neste caso foi estabelecida por Ladner.

Problema P versus NP

Ver artigo principal: Problema P versus NP

A classe de complexidade P é frequentemente vista como uma abstração matemática modelando aquelas tarefas computacionais que admitem um algoritmo eficiente. Essa hipótese é chamada de tese de Cobham-Edmonds. A classe de complexidade NP, por outro lado, contém muitos problemas que as pessoas gostariam de resolver eficientemente, mas para os quais nenhum algoritmo eficiente é conhecido, como o problema de satisfatibilidade booleana, o problema do caminho hamiltoniano e o problema da cobertura de vértices. Como máquinas de Turing determinísticas são máquinas de Turing não determinísticas especiais, é facilmente observado que cada problema em P também é um membro da classe NP.

A questão de saber se P é igual a NP é uma das questões em aberto mais importantes da ciência da computação teórica devido às amplas implicações de uma solução. Se a resposta for sim, muitos problemas importantes podem ser demonstrados como tendo soluções mais eficientes. Estes incluem vários tipos de problemas de programação inteira em pesquisa operacional, muitos problemas em logística, predição de estrutura de proteínas em biologia, e a capacidade de encontrar provas formais de teoremas de matemática pura. O problema P versus NP é um dos Problemas do Prêmio Millennium propostos pelo Clay Mathematics Institute. Há um prêmio de US$ 1.000.000 para a resolução do problema.

Problemas em NP não conhecidos por estar em P ou NP-completo

Foi mostrado por Ladner que se ${\textsf {P}}\neq {\textsf {NP}}$ então existem problemas em ${\textsf {NP}}$ que não estão nem em ${\textsf {P}}$ nem são ${\textsf {NP}}$-completos. Tais problemas são chamados de problemas NP-intermediários. O problema do isomorfismo de grafos, o problema do logaritmo discreto e o problema da fatoração de inteiros são exemplos de problemas que se acredita serem NP-intermediários. Eles são alguns dos poucos problemas NP que não se sabe estarem em ${\textsf {P}}$ ou serem ${\textsf {NP}}$-completos.

O problema do isomorfismo de grafos é o problema computacional de determinar se dois grafos finitos são isomórficos. Um importante problema não resolvido na teoria da complexidade é se o problema do isomorfismo de grafos está em ${\textsf {P}}$, é ${\textsf {NP}}$-completo ou NP-intermediário. A resposta não é conhecida, mas acredita-se que o problema é pelo menos não NP-completo. Se o isomorfismo de grafos é NP-completo, a hierarquia de tempo polinomial colapsa para seu segundo nível. Como se acredita amplamente que a hierarquia polinomial não colapsa para nenhum nível finito, acredita-se que o isomorfismo de grafos não é NP-completo. O melhor algoritmo para este problema, devido a László Babai e Eugene Luks, tem tempo de execução $O(2^{\sqrt {n\log n}})$ para grafos com $n$ vértices, embora alguns trabalhos recentes de Babai ofereçam algumas novas perspectivas sobre isso.

O problema da fatoração de inteiros é o problema computacional de determinar a fatoração em primos de um dado inteiro. Formulado como um problema de decisão, é o problema de decidir se a entrada tem um fator primo menor que $k$. Nenhum algoritmo de fatoração de inteiros eficiente é conhecido, e este fato forma a base de vários sistemas criptográficos modernos, como o algoritmo RSA. O problema da fatoração de inteiros está em ${\textsf {NP}}$ e em ${\textsf {co-NP}}$ (e mesmo em UP e co-UP). Se o problema é ${\textsf {NP}}$-completo, a hierarquia de tempo polinomial colapsará para seu primeiro nível (ou seja, ${\textsf {NP}}$ será igual a ${\textsf {co-NP}}$). O algoritmo conhecido mais eficiente para fatoração de inteiros é a peneira de corpo de números geral, que leva tempo $O(e^{\left({\sqrt[{3}]{\frac {64}{9}}}\right){\sqrt[{3}]{(\log n)}}{\sqrt[{3}]{(\log \log n)^{2}}}})$ para fatorar um inteiro ímpar $n$. No entanto, o algoritmo quântico mais conhecido para este problema, o algoritmo de Shor, é executado em tempo polinomial. Infelizmente, este fato não diz muito sobre onde o problema se situa em relação às classes de complexidade não quânticas.

Separações entre outras classes de complexidade

Muitas classes de complexidade conhecidas são suspeitas de serem desiguais, mas isso não foi provado. Por exemplo, ${\textsf {P}}\subseteq {\textsf {NP}}\subseteq {\textsf {PP}}\subseteq {\textsf {PSPACE}}$, mas é possível que ${\textsf {P}}={\textsf {PSPACE}}$. Se ${\textsf {P}}$ não é igual a ${\textsf {NP}}$, então ${\textsf {P}}$ também não é igual a ${\textsf {PSPACE}}$. Como existem muitas classes de complexidade conhecidas entre ${\textsf {P}}$ e ${\textsf {PSPACE}}$, tais como ${\textsf {RP}}$, ${\textsf {BPP}}$, ${\textsf {PP}}$, ${\textsf {BQP}}$, ${\textsf {MA}}$, ${\textsf {PH}}$, etc., é possível que todas essas classes de complexidade colapsem para uma única classe. Provar que qualquer uma dessas classes é desigual seria um grande avanço na teoria da complexidade.

Na mesma linha, ${\textsf {co-NP}}$ é a classe que contém os problemas complementares (ou seja, problemas com as respostas sim/não invertidas) dos problemas ${\textsf {NP}}$. Acredita-se que ${\textsf {NP}}$ não é igual a ${\textsf {co-NP}}$; no entanto, ainda não foi provado. É claro que se essas duas classes de complexidade não são iguais, então ${\textsf {P}}$ não é igual a ${\textsf {NP}}$, pois ${\textsf {P}}={\textsf {co-P}}$. Assim, se $P=NP$ teríamos ${\textsf {co-P}}={\textsf {co-NP}}$ donde ${\textsf {NP}}={\textsf {P}}={\textsf {co-P}}={\textsf {co-NP}}$.

Similarmente, não se sabe se ${\textsf {L}}$ (o conjunto de todos os problemas que podem ser resolvidos em espaço logarítmico) está estritamente contido em ${\textsf {P}}$ ou é igual a ${\textsf {P}}$. Novamente, existem muitas classes de complexidade entre os dois, como ${\textsf {NL}}$ e ${\textsf {NC}}$, e não se sabe se são distintas ou classes iguais.

Suspeita-se que ${\textsf {P}}$ e ${\textsf {BPP}}$ são iguais. No entanto, está em aberto se ${\textsf {BPP}}={\textsf {NEXP}}$.

Intratabilidade

Ver também: Explosão combinatória

Um problema que pode teoricamente ser resolvido, mas requer uma quantidade impraticavelmente grande, quase infinita, de recursos (por exemplo, tempo) para fazê-lo, é conhecido como um problema intratável. Por outro lado, um problema que pode ser resolvido na prática é chamado de problema tratável, literalmente "um problema que pode ser manejado". O termo inviável (literalmente "não pode ser feito") é às vezes usado como sinônimo de intratável, embora isso possa causar confusão com uma solução viável em otimização matemática.

Problemas tratáveis são frequentemente identificados com problemas que têm soluções de tempo polinomial (${\textsf {P}}$, ${\textsf {PTIME}}$); isso é conhecido como a tese de Cobham-Edmonds. Problemas que são conhecidos por serem intratáveis neste sentido incluem aqueles que são EXPTIME-difíceis. Se ${\textsf {NP}}$ não é o mesmo que ${\textsf {P}}$, então problemas NP-difíceis também são intratáveis neste sentido.

No entanto, essa identificação é imprecisa: uma solução de tempo polinomial com alto grau ou alto coeficiente líder cresce rapidamente e pode ser impraticável para problemas de tamanho prático; inversamente, uma solução de tempo exponencial que cresce lentamente pode ser prática para entradas realistas, ou uma solução que leva muito tempo no pior caso pode levar pouco tempo na maioria dos casos ou no caso médio, e ainda assim ser prática. Dizer que um problema não está em ${\textsf {P}}$ não implica que todos os grandes casos do problema sejam difíceis ou mesmo que a maioria deles seja. Por exemplo, o problema de decisão na aritmética de Presburger foi demonstrado não estar em ${\textsf {P}}$, no entanto, algoritmos foram escritos que resolvem o problema em tempos razoáveis na maioria dos casos. Similarmente, algoritmos podem resolver o problema NP-completo da mochila em uma ampla gama de tamanhos em menos de tempo quadrático e solucionadores SAT rotineiramente lidam com grandes instâncias do problema de satisfatibilidade booleana NP-completo.

Para ver por que algoritmos de tempo exponencial são geralmente inutilizáveis na prática, considere um programa que realiza $2^{n}$ operações antes de parar. Para $n$ pequeno, digamos 100, e assumindo para fins de exemplo que o computador faz $10^{12}$ operações por segundo, o programa seria executado por cerca de $4\times 10^{10}$ anos, que é a mesma ordem de grandeza que a idade do universo. Mesmo com um computador muito mais rápido, o programa só seria útil para instâncias muito pequenas e, nesse sentido, a intratabilidade de um problema é um tanto independente do progresso tecnológico. No entanto, um algoritmo de tempo exponencial que leva $1.0001^{n}$ operações é prático até que $n$ se torne relativamente grande.

Da mesma forma, um algoritmo de tempo polinomial nem sempre é prático. Se seu tempo de execução é, digamos, $n^{15}$, não é razoável considerá-lo eficiente e ainda é inútil, exceto em pequenas instâncias. De fato, na prática, mesmo algoritmos $n^{3}$ ou $n^{2}$ são frequentemente impraticáveis em tamanhos realistas de problemas.

Teoria da complexidade contínua

A teoria da complexidade contínua pode se referir à teoria da complexidade de problemas que envolvem funções contínuas que são aproximadas por discretizações, como estudado em análise numérica. Uma abordagem para a teoria da complexidade da análise numérica é a complexidade baseada em informação.

A teoria da complexidade contínua também pode se referir à teoria da complexidade do uso de computação analógica, que usa sistemas dinâmicos contínuos e equações diferenciais. A teoria de controle pode ser considerada uma forma de computação e equações diferenciais são usadas na modelagem de sistemas de tempo contínuo e híbridos discreto-contínuos.

História

Um exemplo precoce de análise de complexidade de algoritmos é a análise do tempo de execução do algoritmo de Euclides feita por Gabriel Lamé em 1844.

Antes que a pesquisa propriamente dedicada à complexidade de problemas algorítmicos começasse, várias fundações foram estabelecidas por diversos pesquisadores. A mais influente entre elas foi a definição de máquinas de Turing por Alan Turing em 1936, que se revelou uma simplificação muito robusta e flexível de um computador.

O início dos estudos sistemáticos em complexidade computacional é atribuído ao seminal artigo de 1965 "On the Computational Complexity of Algorithms" de Juris Hartmanis e Richard E. Stearns, que estabeleceu as definições de complexidade de tempo e complexidade de espaço, e provou os teoremas da hierarquia. Além disso, em 1965 Edmonds sugeriu considerar um "bom" algoritmo como aquele com tempo de execução limitado por um polinômio do tamanho da entrada.

Artigos anteriores estudando problemas solucionáveis por máquinas de Turing com recursos limitados específicos incluem a definição de autômatos linearmente limitados por John Myhill (Myhill 1960), o estudo de conjuntos rudimentares por Raymond Smullyan (1961), bem como o artigo de Hisao Yamada sobre computações em tempo real (1962). Um pouco antes, Boris Trakhtenbrot (1956), um pioneiro na área da URSS, estudou outra medida de complexidade específica. Como ele recorda:

No entanto, [meu] interesse inicial [na teoria dos autômatos] foi cada vez mais deixado de lado em favor da complexidade computacional, uma empolgante fusão de métodos combinatórios, herdados da teoria dos circuitos de comutação, com o arsenal conceitual da teoria dos algoritmos. Essas ideias me ocorreram em 1955, quando cunhei o termo "função sinalizadora", que hoje é comumente conhecido como "medida de complexidade".

Em 1967, Manuel Blum formulou um conjunto de axiomas (agora conhecidos como axiomas de Blum) especificando propriedades desejáveis de medidas de complexidade no conjunto de funções computáveis e provou um resultado importante, o chamado teorema da aceleração. O campo começou a florescer em 1971, quando Stephen Cook e Leonid Levin provaram a existência de problemas praticamente relevantes que são NP-completos. Em 1972, Richard Karp levou essa ideia adiante com seu artigo marcante, "Reducibility Among Combinatorial Problems", no qual mostrou que 21 diversos problemas combinatórios e de grafos, cada um notório por sua intratabilidade computacional, são NP-completos.

Ver também

• Complexidade computacional
• Teoria da complexidade descritiva
• Complexidade de jogos
• Linguagem folha
• Limites da computação
• Lista de classes de complexidade
• Lista de tópicos sobre computabilidade e complexidade
• Lista de problemas não resolvidos da ciência da computação
• Complexidade parametrizada
• Complexidade de prova
• Teoria da complexidade quântica
• Teoria da complexidade estrutural
• Problema transcomputacional
• Complexidade computacional de operações matemáticas

Obras sobre complexidade

• Wuppuluri, Shyam; Doria, Francisco A., eds. (2020), Unravelling Complexity: The Life and Work of Gregory Chaitin, ISBN 978-981-12-0006-9, World Scientific, doi:10.1142/11270 

Bibliografia

• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, ISBN 978-0-521-42426-4, Cambridge University Press, Zbl 1193.68112 
• Downey, Rod; Fellows, Michael (1999), Parameterized complexity, ISBN 9780387948836, Monographs in Computer Science, Berlin, New York: Springer-Verlag 
• Du, Ding-Zhu; Ko, Ker-I (2000), Theory of Computational Complexity, ISBN 978-0-471-34506-0, John Wiley & Sons 
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press 
• van Leeuwen, Jan, ed. (1990), Handbook of theoretical computer science (vol. A): algorithms and complexity, ISBN 978-0-444-88071-0, MIT Press 
• Papadimitriou, Christos (1994), Computational Complexity, ISBN 978-0-201-53082-7 1ª ed. , Addison Wesley 
• Sipser, Michael (2006), Introduction to the Theory of Computation, ISBN 978-0-534-95097-2 2ª ed. , USA: Thomson Course Technology 

Pesquisas

• Khalil, Hatem; Ulery, Dana (1976), «A review of current studies on complexity of algorithms for partial differential equations», Proceedings of the annual conference on – ACM 76, ISBN 9781450374897, pp. 197–201, doi:10.1145/800191.805573 
• Cook, Stephen (1983), «An overview of computational complexity», Communications of the ACM, ISSN 0001-0782, 26 (6): 400–408, doi:10.1145/358141.358144 
• Fortnow, Lance; Homer, Steven (2003), «A Short History of Computational Complexity» (PDF), Bulletin of the EATCS, 80: 95–133 
• Mertens, Stephan (2002), «Computational Complexity for Physicists», Computing in Science & Engineering, ISSN 1521-9615, 4 (3): 31–47, Bibcode:2002CSE.....4c..31M, arXiv:cond-mat/0012185, doi:10.1109/5992.998639 

Ligações externas

• The Complexity Zoo
• Hazewinkel, Michiel, ed. (2001), «Computational complexity classes», Enciclopédia de Matemática, ISBN 978-1-55608-010-4 (em inglês), Springer 
• Scott Aaronson: Why Philosophers Should Care About Computational Complexity