Mostrar código-fonte de Complexidade computacional

A '''teoria da complexidade computacional''' é um ramo da [[teoria da computação]] em [[ciência da computação teórica]] e [[matemática]] que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si. Neste contexto, um problema computacional é entendido como uma tarefa que é, em princípio, passível de ser resolvida por um computador (o que basicamente significa que o problema pode ser descrito por um conjunto de instruções matemáticas). Informalmente, um problema computacional consiste de instâncias do problema e soluções para essas instâncias do problema. Por exemplo, o [[teste de primalidade]] é o problema de determinar se um dado número é [[Número primo|primo]] ou não. As instâncias deste problema são [[Número natural|números naturais]], e a solução para uma instância é ''sim'' ou ''não'', dependendo se o número é primo ou não.

Um problema é considerado como inerentemente difícil se a sua solução requer recursos significativos, qualquer que seja o algoritmo usado. A teoria formaliza esta intuição através da introdução de [[Modelo de computação|modelos matemáticos de computação]] para estudar estes problemas e quantificar os recursos necessários para resolvê-los, tais como tempo e armazenamento. Outras medidas de complexidade também são utilizadas, tais como a quantidade de comunicação (usada em [[complexidade de comunicação]]), o número de [[Portas lógicas|portas]] em um circuito (usado na [[complexidade de circuito]]) e o número de processadores (usados em [[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.

Campos intimamente relacionados com a ciência da computação teórica são a [[análise de algoritmos]] e a [[teoria da computabilidade]]. Uma distinção chave entre a análise de algoritmos e teoria da complexidade computacional é que a primeira é dedicada a analisar a quantidade de recursos necessários para um determinado algoritmo resolver um problema, enquanto o segundo faz uma pergunta mais geral sobre todos os possíveis algoritmos que podem ser usados para resolver o mesmo problema. Mais precisamente, ele tenta classificar os problemas que podem ou não podem ser resolvidos com os recursos devidamente restritos. Por sua vez, impondo restrições sobre os recursos disponíveis é o que distingue a complexidade computacional da teoria da computabilidade: a segunda pergunta que tipos de problemas podem, em princípio, ser resolvidos através de algoritmos.

==Problemas Computacionais==
[[Imagem:TSP Deutschland 3.png|thumb|200px|Um caminho ótimo para o caixeiro viajante passando pelas 15 maiores cidades da Alemanha. É o menor caminho entre as 43.589.145.600<ref group="nb">Escolha uma cidade, e pegue todas as ordenações possíveis das outras 14 cidades. Depois divida por dois, porque não importa em qual direção pelo tempo elas vêm uma após a outra: 14 / 2 = 43.589.145.600.</ref> possibilidades de se visitar cada cidade exatamente uma única vez]]

===Instâncias de Problema===
Um [[problema computacional]] pode ser visto como uma coleção infinita de ''instâncias'' em conjunto com uma ''solução'' para cada instância. A sequência de entrada para um problema computacional é referido como uma instância do problema, e não deve ser confundido com o problema em si. Na teoria da complexidade computacional, um problema se refere à questão abstrata para ser resolvido. Em contraste, uma instância deste problema é uma expressão concreta, 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, 10) e a solução é "sim" se o número é primo e "não" se for o contrário (neste caso "não"). Alternativamente, a instância é uma entrada especial para o problema, e a solução é a saída correspondente à entrada.

Para realçar 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 um percurso de, no máximo, 2000&nbsp;km de comprimento passando por todas as 15 maiores cidades da [[Alemanha]]? A resposta a esta determinada instância do problema é de pouca utilidade para a resolução de outras instâncias do problema, como pedir uma ida e volta através de todos os lugares de Milão cujo comprimento total é no máximo 10&nbsp;km. Por esta razão, a teoria da complexidade aborda problemas computacionais e não instâncias particulares do problema.

===Representando instâncias de problema===
Ao considerar problemas computacionais, uma instância de problema é uma cadeia sobre um alfabeto. Normalmente, o alfabeto é considerado como sendo o alfabeto binário (ou seja, o conjunto {0,1}), e, assim, as cadeias são bitstrings. Como em um computador do mundo real, objetos matemáticos que não são bitstrings devem ser devidamente codificados. Por exemplo, [[Número inteiro|números inteiros]] podem ser representados em [[Sistema binário (matemática)|notação binária]], e [[grafo]]s podem ser codificados diretamente via suas [[Matriz de adjacência|matrizes de adjacência]], ou por codificação de suas [[Lista de adjacência|listas de adjacência]] em binário.

Apesar de algumas provas de complexidade-teórica de teoremas regularmente assumir alguma escolha concreta de codificação de entrada, tenta-se manter a discussão abstrata o suficiente para ser independente da escolha da codificação. Isto pode ser conseguido assegurando que diferentes representações possam ser transformadas em outra de forma eficiente.

[[Imagem:Decisao.png|thumb|200px|Um problema de decisão tem apenas duas saídas possíveis, ''sim'' ou ''não'' (ou alternativamente 1 ou 0) para qualquer entrada]]

===Problemas de decisão como linguagens formais===
[[Problema de decisão|Problemas de decisão]] são um dos objetos de estudo centrais na teoria da complexidade computacional. Um problema de decisão é um tipo especial de problema computacional cuja resposta é sim ou não, ou 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 resposta é ''sim'', e os não membros da linguagem são aquelas instâncias cuja saída é ''não''. O objetivo é decidir, com a ajuda de um [[algoritmo]], se uma dada sequência de entrada é um membro da linguagem formal em consideração. Se o algoritmo decidir este problema, ele retorna a resposta ''sim'', diz-se que o algoritmo aceita a sequência de entrada, caso contrário, diz-se que rejeita a entrada.

Um exemplo de um problema de decisão é o seguinte. A entrada é um grafo arbitrário. O problema consiste em decidir se o dado grafo é conexo ou não. A linguagem formal associada a este problema de decisão é então o conjunto de todos os grafos conexos—obviamente, para obter uma definição precisa dessa linguagem, é preciso decidir como 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 parcial|função total]]) é esperada para cada entrada, mas a saída é mais complexa do que a de um problema de decisão, isto é, não é apenas sim ou não. Exemplos notáveis incluem o problema do caixeiro viajante e o [[Fatoração de inteiros|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, o caso realmente não é esse, já que problemas de função podem ser reformulados como problemas de decisão. Por exemplo, a multiplicação de dois números inteiros pode ser expressa como o conjunto (''a'',&nbsp;''b'',&nbsp;''c'') tal qual a relação ''a''&nbsp;×&nbsp;''b''&nbsp;=&nbsp;''c'' descreve. Decidir se uma dada tripla é membro deste conjunto corresponde a resolver o problema da multiplicação de dois números.

===Mensuração  do tamanho de uma instância===
Para medir a dificuldade de resolver um problema computacional, pode-se desejar ver quanto tempo o melhor algoritmo necessita 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 resolver. Assim, o tempo necessário para resolver um problema (ou o espaço necessário, ou qualquer outra medida de complexidade) é calculado em função do tamanho da instância. Isso geralmente leva em consideração o tamanho da entrada em bits. A Teoria da Complexidade está interessada em como os tempos de execução de algoritmos crescem com um aumento no tamanho da entrada. Por exemplo, no problema de descobrir se um grafo é conectado, quanto tempo a mais leva para resolver um problema para um grafo com 2''n'' vértices comparado ao tempo levado 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''. Já que o tempo gasto em diferentes entradas de mesmo tamanho pode ser diferente, o pior caso em complexidade de tempo T(''n'') é definido como sendo o tempo máximo dentre todas as entradas de tamanho ''n''. Se T(''n'') é um polinômio em ''n'', então o algoritmo é dito ser um algoritmo de [[tempo polinomial]]. A [[tese de Cobham]] diz que um problema pode ser resolvido com uma quantidade factível de recursos se ele admite um algoritmo de tempo polinomial.

==Modelos de máquinas e medidas de complexidade==
===Máquina de Turing===
[[Imagem:Maquina.png|thumb|Uma representação artística de uma máquina de Turing]]
{{Artigo principal|Máquina de Turing}}
Uma máquina de Turing é um modelo matemático de uma máquina de computação em geral. É um dispositivo teórico que manipula símbolos contidos em uma tira de fita. Máquinas de Turing não pretendem ser uma tecnologia de computação na prática, mas sim uma experiência de pensamento que representa uma máquina de computação. Acredita-se que se um problema pode ser resolvido por um algoritmo, então existe uma máquina de Turing que resolve o problema. Na verdade, 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 conhecido por nós hoje, como uma máquina RAM, [[Jogo da vida|Jogo da Vida de Conway]], [[Autómato celular|autômato celular]] 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 em teoria da complexidade.

Muitos tipos de máquinas de Turing são usados para definir as [[Classe de complexidade|classes de complexidade]], tais como [[Máquina de Turing|máquinas de Turing determinísticas]], [[Máquina de Turing probabilística|máquinas de Turing probabilísticas]], [[Máquina de Turing não determinística|máquinas de Turing não-determinísticas]], [[Máquina de Turing quântica|máquinas de Turing quânticas]], [[Máquina de Turing simétrica|máquinas de Turing simétricas]] e [[Máquina de Turing alternada|máquinas de Turing alternadas]]. Todas elas são igualmente poderosas, em princípio, mas quando os recursos (tais como tempo e espaço) são limitados, algumas destas podem ser mais poderosas do que outras.

Uma máquina de Turing determinística é a máquina de Turing do tipo mais básico, que utiliza 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 muitas vezes ajuda algoritmos a resolverem problemas de forma mais eficiente. Algoritmos que usam bits aleatórios são chamados [[Algoritmo probabilístico|algoritmos probabilísticos]]. A máquina de Turing não-determinística é uma máquina de Turing determinística com uma característica adicional de não-determinismo, que permite que uma máquina de Turing tenha várias possíveis ações futuras a partir de um determinado estado. Uma maneira de entender o não-determinismo é visualizar os ramos da máquina de Turing como os vários caminhos computacionais possíveis a cada passo, e se ela resolve o problema em qualquer um desses ramos, diz-se ter resolvido o problema. Evidentemente, 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. Por exemplo, veja algoritmo não-determinístico.

===Outros modelos de máquinas===
Muitos modelos de máquinas diferentes do padrão de [[Máquina de Turing multifita|máquinas de Turing multi-fitas]] têm sido propostos na literatura, por exemplo, máquinas de acesso aleatório. Talvez surpreendentemente, cada um desses modelos pode ser convertido para outro, sem fornecer qualquer poder computacional extra. O consumo de tempo e memória desses modelos alternativos pode variar.<ref>Veja {{harvnb|Arora|Barak|2009|loc=Chapter 1: The computational model and why it doesn't matter}}</ref> O que todos estes modelos têm em comum é que as máquinas funcionam 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 em que é permitido ramificar-se para verificar muitas possibilidades diferentes de uma só vez. A máquina de Turing não-determinística tem muito pouco a ver com a forma como nós queremos fisicamente computar algoritmos, mas a sua ramificação capta 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 utilizando uma determinada quantidade de tempo e espaço, um modelo computacional tal como a máquina de Turing determinística é utilizado. O ''tempo exigido'' por uma máquina de Turing determinística ''M'' na entrada ''x'' é o número total de transições de estado, ou etapas, que a máquina faz antes de parar e responder com a saída ("sim" ou "não"). Diz-se que a máquina de Turing ''M'' opera dentro do tempo ''f''(''n''), se o tempo exigido 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 operação da máquina de Turing em tempo ''f''(''n'') que resolve o problema. Como a teoria da complexidade está interessada em classificar problemas com base na sua dificuldade, definem-se conjuntos de problemas com base em alguns critérios. Por exemplo, o conjunto de problemas solucionáveis no tempo ''f''(''n'') em uma máquina de Turing determinística é então indicado por [[DTIME]](''f''(''n'')).

Definições análogas podem ser feitas para os requisitos de espaço. Embora o tempo e o espaço sejam os mais conhecidos recursos de complexidade, qualquer medida de complexidade pode ser vista como um recurso computacional. [[Medidas de complexidade]] são geralmente definidas pelos [[Axiomas de Blum|axiomas de complexidade de Blum]]. Outras medidas de complexidade utilizadas na teoria da complexidade incluem a [[complexidade de comunicação]], a [[complexidade do circuito]] e a [[Modelo de árvore de decisão|complexidade da árvore de decisão]].

===Melhor, pior e caso médio de complexidade===
[[Imagem:Sorting quicksort anim.gif|thumb|250px|Visualização do algoritmo quicksort que tem no caso médio desempenho <math>\Theta(n\log n).</math>]]
O melhor, o pior e o caso médio de complexidade referem-se a três maneiras diferentes de medir a complexidade de tempo (ou qualquer outra medida de complexidade) de entradas diferentes do mesmo tamanho. Uma vez que algumas entradas de tamanho ''n'' podem ser mais rápidas para resolver do que outras, definimos as seguintes complexidades:
*Complexidade no melhor caso: Esta é a complexidade de resolver o problema para a melhor entrada de tamanho ''n''.
*Complexidade no pior caso: Esta é a complexidade de resolver o problema para a pior entrada de tamanho ''n''.
*Complexidade no caso médio: Esta é a complexidade de resolver o problema na média. Essa complexidade só é definida com relação a uma [[distribuição de probabilidade]] sobre as entradas. Por exemplo, se todas as entradas do mesmo tamanho são consideradas terem a mesma probabilidade de aparecer, a complexidade do caso médio pode ser definida com relação à distribuição uniforme sobre todas as entradas de tamanho ''n''.

Por exemplo, considere o algoritmo de ordenação [[quicksort]]. Isso resolve o problema de ordenar uma lista de inteiros que é dada como entrada. O pior caso é quando a entrada já está ordenada ou está em ordem inversa, e o algoritmo leva tempo O(''n''<sup>2</sup>) para este caso. Se assumirmos que todas as permutações possíveis da lista de entrada são igualmente prováveis, o tempo médio necessário para a ordenação é O(''n'' log ''n''). O melhor caso ocorre quando cada pivô divide a lista pela metade, também precisando tempo O(''n'' log ''n'').

===Limites superior e inferior da complexidade dos problemas===
Para classificar o tempo de computação (ou recursos semelhantes, como o consumo de espaço), é necessário provar os limites superiores e inferiores sobre a quantidade mínima de tempo exigida pelo algoritmo mais eficiente para resolver um determinado problema. A complexidade de um algoritmo é geralmente entendida como a sua complexidade de pior caso, a menos que seja especificado o contrário. A análise de um determinado algoritmo cai sob o campo de análise de algoritmos. Para mostrar um limite superior ''T''(''n'') sobre a complexidade de tempo de um problema, é necessário mostrar apenas que há um determinado algoritmo com tempo de funcionamento, no máximo, ''T''(''n''). No entanto, provar limites inferiores é muito mais difícil, uma vez que limites inferiores fazem uma declaração sobre todos os possíveis algoritmos 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. Para mostrar um limite inferior de ''T''(''n'') para um problema requer mostrar que nenhum algoritmo pode ter complexidade de tempo menor do que ''T''(''n'').

Limites superiores  são geralmente indicados usando a [[Grande-O|notação O-grande]], que desconsidera fatores constantes e termos menores. Isso faz com que os limites independam dos detalhes específicos do modelo computacional utilizado. Por exemplo, ''T''(''n'')&nbsp;=&nbsp;7''n''<sup>2</sup>&nbsp;+&nbsp;15''n''&nbsp;+&nbsp;40, em notação O-grande seria escrito da seguinte forma ''T''(''n'')&nbsp;=&nbsp;O(''n''<sup>2</sup>).

Limites inferiores são geralmente indicados usando a notação Ω

==Classes de complexidade==
===Definição de classes de complexidade===
Uma '''classe de complexidade''' é um conjunto de problemas de complexidade relacionados. As classes mais simples de complexidade são definidas pelos seguintes fatores:
* O tipo de problema computacional: Os problemas mais comumente utilizados são 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 mais comum de computação é 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 os limites: Essas duas propriedades são geralmente declaradas em conjunto, tais como "tempo polinomial", "espaço logarítmico", "profundidade constante", etc.

É claro, algumas classes de complexidade têm definições complexas que não se encaixam nesse quadro. Assim, uma classe de complexidade típica tem uma definição como a seguinte:

:O conjunto de problemas de decisão solú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'') muitas vezes produz classes de complexidade que dependem do modelo da máquina escolhida. Por exemplo, a linguagem {''xx'' | ''x'' é uma sequência binária qualquer} pode ser resolvida em tempo linear em uma máquina de Turing multi-fitas, mas necessariamente exige tempo quadrático no modelo de máquinas de Turing single-fita. Se permitirmos variações no tempo polinomial em execução, a [[tese de Cobham-Edmonds]] afirma que "as complexidades do tempo em quaisquer dois modelos razoáveis e gerais de computação são polinomialmente relacionados" {{Harv|Goldreich|2008|loc=Chapter 1.2}}. Isto forma a base para a classe de complexidade P, que é o conjunto de problemas de decisão solúveis por uma máquina de Turing determinística dentro do tempo polinomial. O conjunto correspondente de problemas de função é FP.

===Importantes classes de complexidade===
[[Imagem:Complexity subsets pspace.svg|300px|thumb|right|Uma representação da relação entre as classes de complexidade]]
Muitas classes de complexidade importantes podem ser definidas por limitando o tempo ou espaço usado pelo algoritmo. Algumas importantes classes de complexidade de problemas de decisão definidas desta maneira são as seguintes:

{| class="wikitable"
|-

! Classe de complexidade

! Modelo de computação

! Limitação de recursos
|-
| [[DTIME]](''f''(''n''))
| Máquina de Turing Determinística
| Tempo ''f''(''n'')
|-
| [[P (complexidade)|P]]
| Máquina de Turing Determinística
| Tempo poly(''n'')
|-
| [[EXPTIME]]
| Máquina de Turing Determinística
| Tempo 2<sup>poly(''n'')</sup>
|-
| [[NTIME]](''f''(''n''))
| Máquina de Turing Não-Determinística
| Tempo ''f''(''n'')
|-
| [[NP (complexidade)|NP]]
| Máquina de Turing Não-Determinística
| Time poly(''n'')
|-
| [[NEXPTIME]]
| Máquina de Turing Não-Determinística
| Tempo 2<sup>poly(''n'')</sup>
|-
| [[DSPACE]](''f''(''n''))
| Máquina de Turing Determinística
| Espaço ''f''(''n'')
|-
| [[LSPACE|L]]
| Máquina de Turing Determinística
| Espaço O(log ''n'')
|-
| [[PSPACE]]
| Máquina de Turing Determinística
| Espaço poly(''n'')
|-
| [[EXPSPACE]]
| Máquina de Turing Determinística
| Espaço 2<sup>poly(''n'')</sup>
|-
| [[NSPACE]](''f''(''n''))
| Máquina de Turing Não-Determinística
| Espaço ''f''(''n'')
|-
| [[NL (complexity)|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 poly(''n'')
|-
| [[NEXPSPACE]]
| Máquina de Turing Não-Determinística
| Espaço 2<sup>poly(''n'')</sup>
|}

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ística; [[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. [[Sharp-P|#P]] é uma importante classe complexidade de problemas de contagem (que não são problemas de decisão). Classes como [[IP-Complexidade|IP]] e [[Arthur–Merlin protocol|AM]] são definidas usando sistemas de prova interativa. ALL é a classe de todos os problemas de decisão.

===Teoremas de hierarquia===
Para as classes de complexidade definidas desta forma, é desejável provar que relaxar os requisitos em função (digamos) do tempo de computação realmente define um conjunto maior de problemas. Em particular, embora DTIME(''n'') esteja contido em DTIME(''n''<sup>2</sup>), seria interessante saber se a inclusão é estrita. Para requisitos de tempo e de espaço, a resposta a tais perguntas é dada pelo teorema de hierarquia para a complexidade de tempo e pelo teorema de hierarquia para a complexidade de espaço, respectivamente. Eles são chamados teoremas de hierarquia porque induzem uma hierarquia adequada sobre as classes definidas, restringindo os respectivos recursos. Assim, existem pares de classes de complexidade tal que uma está propriamente contida na outra. Depois de ter deduzido assim as relações de pertinência estrita de conjuntos, podemos continuar a fazer declarações quantitativas sobre quanto mais tempo adicional ou espaço é necessário para aumentar o número de problemas que podem ser resolvidos.

Mais precisamente, o teorema de hierarquia de tempo afirma que:
<math display="block">\operatorname{DTIME}\big(f(n) \big) \subsetneq \operatorname{DTIME} \big(f(n) \sdot \log^{2}(f(n)) \big).</math>

O teorema de hierarquia de espaço afirma que:
<math display="block">\operatorname{DSPACE}\big(f(n)\big) \subsetneq \operatorname{DSPACE} \big(f(n) \sdot \log(f(n)) \big).</math>

Os teoremas de hierarquia de tempo e de 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 contida em EXPTIME, e o teorema hierarquia do espaço nos diz que L está estritamente contida em PSPACE.

===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. Ela captura a noção informal de um problema que seja pelo menos 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ção, com base no método de redução, como reduções de Cook, reduções de Karp e reduções Levin, e no limite da complexidade das reduções, como reduções de tempo polinomial ou reduções log-space.

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

Isso motiva o conceito de um problema que 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'', uma vez que um algoritmo para ''X'' nos permite resolver qualquer problema em ''C''. É claro que a noção de problemas difíceis depende do tipo de redução a ser utilizado. Para as classes de complexidade maiores do que P, reduções em tempo polinomial são comumente usados. Em particular, o conjunto de problemas que são difíceis para NP é o conjunto de problemas [[NP-difícil]].

Se um problema ''X'' está em ''C'' e é ''difícil'' para ''C'', então diz-se que ''X'' é completo para ''C''. Isto significa que ''X'' é o problema mais difícil em ''C''. (Uma vez que muitos problemas poderiam ser igualmente difíceis, pode-se dizer que ''X'' é um dos os problemas mais difíceis em ''C''.) Assim, a classe de [[NP-completo|problemas NP-completo]] contém os problemas mais difíceis em NP, nesse sentido eles são os mais propensos a não estarem em P. Como o problema P&nbsp;=&nbsp;NP não foi resolvido, ser capaz de reduzir um conhecido problema NP-completo, Π<sub>2</sub>, para outro problema, Π<sub>1</sub>, indicaria que não há nenhuma solução conhecida em tempo polinomial para Π<sub>1</sub>. Isso ocorre porque uma solução em tempo polinomial para Π<sub>1</sub> renderia uma solução em tempo polinomial para Π<sub>2</sub>. Da mesma forma que todos os problemas NP podem ser reduzidos ao conjunto, encontrar um problema NP-completo que pudesse ser resolvido em tempo polinomial significaria que P&nbsp;=&nbsp;NP.<ref name="Sipser2006"/>

==Importantes problemas em aberto==
[[Imagem:Complexity classes.svg|thumb|250px|Diagrama de classes de complexidade assumindo que P&nbsp;≠&nbsp;NP. A existência de problemas em NP fora tanto de P quanto de NP-completo, neste caso, foi estabelecida por Ladner.<ref name="Ladner75">{{Citation|último=Ladner|primeiro=Richard E.|título=On the structure of polynomial time reducibility|periódico=[[Journal of the ACM]] (JACM)|volume=22|ano=1975|páginas=151–171|url=http://delivery.acm.org/10.1145/330000/321877/p155-ladner.pdf?key1=321877&key2=7146531911&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618|formato=PDF|doi=10.1145/321864.321877|número=1|postscript=.}}</ref>]]

===O problema P versus NP===
{{Artigo principal|P versus NP}}
A classe de complexidade P é muitas vezes vista como uma abstração matemática de modelagem dessas tarefas computacionais que admitem um algoritmo eficiente. Esta 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 de forma eficiente, mas para os quais nenhum algoritmo eficiente é conhecido, como o [[Problema de satisfatibilidade booleana|problema da satisfatibilidade booleana]], o [[problema do caminho hamiltoniano]] e o [[Cobertura de vértices (teoria dos grafos)|problema da cobertura de vértices]]. Como as máquinas de Turing determinística são máquinas de Turing não-determinísticas especiais, é fácil observar que cada problema em P também é membro da classe NP.

A questão de saber se P é igual a NP é uma das questões mais importantes em aberto na ciência da computação teórica por causa da gama de implicações de uma solução.<ref name="Sipser2006">Veja {{harvnb|Sipser|2006|loc= Chapter 7: Time complexity}}</ref> Se a resposta for sim, para muitos problemas importantes pode ser mostrado que há soluções mais eficientes para eles. Estes incluem vários tipos de problemas de [[programação inteira]] em [[investigação operacional]], muitos problemas na área de [[logística]], [[previsão da estrutura de proteínas]] na biologia,<ref>{{Citation|título=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete|último=Berger|primeiro=Bonnie A.|periódico=Journal of Computational Biology|ano=1998|volume=5|páginas=27–40|pmid=9541869|doi=10.1089/cmb.1998.5.27|último2=Leighton|primeiro2=T|número=1|postscript=. }}</ref> e capacidade de encontrar provas formais de teoremas da [[matemática pura]].<ref>{{Citation|último=Cook|primeiro=Stephen|autorlink=Stephen Cook|título=The P versus NP Problem|publicado=[[Clay Mathematics Institute]]|data=abril de 2000|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|acessodata=2006-10-18|postscript=.|arquivourl=https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|arquivodata=2010-12-12}}</ref> O problema [[P versus NP]] é um dos [[Problemas do Prémio Millenium|Problemas do Prêmio Millenium]] (Millenium Prize Problems) proposto pelo [[Clay Mathematics Institute|Instituto Clay de Matemática]] (Clay Mathematics Institute). Existe um prêmio de um milhão de [[Dólar|dólares]] para resolver o problema.<ref>{{Citation|título=The Millennium Grand Challenge in Mathematics|último=Jaffe|primeiro=Arthur M.|autorlink=Arthur Jaffe|ano=2006|periódico=Notices of the AMS|volume=53|número=6|url=http://www.ams.org/notices/200606/fea-jaffe.pdf|acessodata=2006-10-18|postscript=.}}</ref>

===Problemas em NP que não se sabe se pertencem a P ou a NP-completo===
Foi mostrado por Ladner que, se '''P ≠ NP''', então existem problemas em '''NP''' que não estão nem em '''P''' nem em '''NP-completo'''.<ref name="Ladner75" /> Tais problemas são chamados de problemas [[NP-intermediário]]. O problema do [[Isomorfismo grafos|isomorfismo de grafos]], o [[Logaritmo discreto|problema do logaritmo discreto]] e o problema de [[fatoração de inteiros]] são exemplos de problemas que acredita-se que sejam NP-intermediário. Eles são alguns dos muito poucos problemas NP que não se sabe se estão em '''P''' ou em '''NP-completo'''.

O problema do isomorfismo de grafos é o problema computacional para determinar se dois grafos finitos são isomorfos. Um importante problema não resolvido na teoria da complexidade é se o problema do isomorfismo de grafos está em '''P''', '''NP-completo''', ou NP-intermediário. A resposta não é conhecida, mas acredita-se que o problema não seja, pelo menos, NP-completo.<ref name="AK06">{{Citation |primeiro1= Vikraman |último1= Arvind |primeiro2= Piyush P. |último2= Kurur |título= Graph isomorphism is in SPP |periódico= Information and Computation | volume = 204 |número= 5 |ano= 2006 |páginas= 835–852 | doi = 10.1016/j.ic.2006.02.002 | postscript = .}}</ref> Se o isomorfismo de grafos for NP-completo, a hierarquia de tempo polinomial colapsa para seu segundo nível.<ref>[[Uwe Schöning]], "Graph isomorphism is in the low hierarchy", Proceedings of the 4th Annual [[Symposium on Theoretical Aspects of Computer Science]], 1987, 114–124; also: ''Journal of Computer and System Sciences'', vol. 37 (1988), 312–323</ref> Uma vez que acredita-se veemente que a hierarquia polinomial não colapse para nenhum nível finito, acredita-se que o isomorfismo de grafos não seja NP-completo. O melhor algoritmo para este problema, de acordo com [[László Babai|Laszlo Babai]] e [[Eugene Luks]] tem tempo de execução 2<sup>O(√(''n'' log(''n'')))</sup> para grafos com ''n'' vértices.

O problema da fatoração de inteiros é o problema computacional para determinar a fatoração prima de um dado inteiro. Formulado como um problema de decisão, é o problema para decidir se a entrada tem um fator menor que ''k''. Nenhum algoritmo de fatoração de inteiro eficiente é conhecido, e este fato é a base de vários sistemas criptográficos modernos, como o algoritmo [[RSA]]. O problema da fatoração de inteiros está em '''NP''' e em '''co-NP''' (e até mesmo em UP e co-UP<ref>[[Lance Fortnow]]. Computational Complexity Blog: Complexity Class of the Week: Factoring. September 13, 2002. http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html</ref>). Se o problema é '''NP-completo''', a hierarquia de tempo polinomial colapsará para seu primeiro nível (ou seja, '''NP''' será igual a '''co-NP'''). O melhor algoritmo conhecido para fatoração de inteiros é o [[GNFS]] (general number field sieve), que leva tempo O(e<sup>(64/9)<sup>1/3</sup>(''n''.log 2)<sup>1/3</sup>(log (''n''.log 2))<sup>2/3</sup></sup>) para fatorar um inteiro de ''n''-bit. No entanto, o melhor algoritmo quântico conhecido para este problema, o [[algoritmo de Shor]], é executado em tempo polinomial. Infelizmente, este fato não diz muito sobre onde está o problema com relação a classes de complexidade não-quântica.

===Separações entre outras classes de complexidade===
Muitas classes de complexidade conhecidas são suspeitas de não serem iguais, mas isso não foi provado. Por exemplo, '''P''' ⊆ '''NP''' ⊆ '''PP''' ⊆ '''PSPACE''', mas é possível que '''P''' = '''PSPACE'''. Se '''P''' não for igual a '''NP''', então '''P''' não será igual à '''PSPACE''' também. Uma vez que existem muitas classes de complexidade conhecidas entre '''P''' e '''PSPACE''', tais como '''RP''', '''BPP''', '''PP''', '''BQP''', '''MA''', '''PH''', etc, é possível que todas estas classes de complexidade colapsem para uma única classe. Provar que qualquer uma destas classes não são iguais seria um grande avanço na teoria da complexidade.

Na mesma linha, '''co-NP''' é a classe que contém os problemas do complemento (ou seja, problemas com as respostas sim / não invertidas) dos problemas '''NP'''. Acredita-se<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> que '''NP''' não seja igual a '''co-NP''', no entanto, ainda não foi comprovado. Tem sido mostrado que, se essas duas classes de complexidade não são iguais, então '''P''' não é igual a '''NP'''.

Da mesma forma, não se sabe se '''L''' (o conjunto de todos os problemas que podem ser resolvidos no espaço logarítmico) está contido estritamente em '''P''' ou é igual a '''P'''. Novamente, existem muitas classes de complexidade entre elas, tais como '''NL''' e '''NC''', e não se sabe se elas são classes iguais ou distintas.

Suspeita-se que '''P''' e '''BPP''' sejam iguais. No entanto, é um problema em aberto, no momento, se '''BPP''' = '''NEXP'''.

==Intratabilidade==
Problemas que podem ser resolvidos na teoria (por exemplo, dado um tempo infinito), mas que na prática levam muito tempo para as suas soluções sejam úteis, são conhecidos como problemas ''intratáveis''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Na teoria da complexidade, os problemas que não apresentam soluções em tempo polinomial são considerados intratáveis por mais pequenas que sejam suas entradas. Na verdade, a tese de Cobham-Edmonds afirma que apenas os problemas que podem ser resolvidos em tempo polinomial podem ser computados de maneira factível por algum dispositivo computacional. Problemas que são conhecidos por serem intratáveis neste sentido incluem aqueles que são EXPTIME-difícil. Se NP não é o mesmo que P, então os problemas NP-completo são também intratáveis neste sentido. Para ver porque algoritmos de tempo exponencial podem ser impraticáveis, considere um programa que faz 2<sup>''n''</sup> operações antes de parar. Para ''n'' pequeno, digamos 100, e assumindo, por exemplo, que o computador faz 10<sup>12</sup> operações por segundo, o programa seria executado por cerca de 4&nbsp;×&nbsp;10<sup>10</sup> anos, que é aproximadamente a idade do universo. Mesmo com um computador muito mais rápido, o programa só seria útil para casos muito pequenos e, nesse sentido, a intratabilidade de um problema é um tanto independente do progresso tecnológico. No entanto, um algoritmo de tempo polinomial não é sempre prático. Se seu tempo de execução é, digamos "n"<sup>15</sup>, não é razoável considerá-lo eficiente e ainda é inútil, salvo em casos de pequeno porte.

O que intratabilidade significa na prática está aberto em debate. Dizer que um problema não está em P não implica que todos os grandes casos de problemas são difíceis ou até mesmo que a maioria deles são. Por exemplo, o problema da decisão na [[Aritmética de Presburger]] tem demonstrado não estar em P, ainda foram escritos algoritmos que resolvem o problema em tempos razoáveis na maioria dos casos. Da mesma forma, os algoritmos podem resolver o [[problema da mochila]] NP-completo em uma ampla faixa de tamanhos em menos que o tempo quadrático e [[Problema de satisfatibilidade booleana|resolvedores de SAT]] rotineiramente lidam com grandes instâncias do problema de satisfatibilidade booleana NP-completo.

==Teoria da complexidade contínua==
A teoria da complexidade contínua pode se referir à teoria da complexidade dos 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<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.4678&rep=rep1&type=pdf Complexity Theory and Numerical Analysis], Steve Smale, Acta Numerica, 1997 - Cambridge Univ Press</ref> é a complexidade baseada em informação (IBC).

A teoria da complexidade contínua também pode se referir à teoria da complexidade do uso da computação analógica, que utiliza [[sistemas dinâmicos]] contínuos e [[Equação diferencial|equações diferenciais]].<ref>[http://arxiv.org/abs/arxiv:0907.3117 A Survey on Continuous Time Computations], Olivier Bournez, Manuel Campagnolo, New Computational Paradigms. Changing Conceptions of What is Computable. (Cooper, S.B. and L{\"o}we, B. and Sorbi, A., Eds.). New York, Springer-Verlag, pages 383-423. 2008</ref> [[Regulação|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 de tempo discreto-contínuo.<ref>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.4296&rep=rep1&type=pdf Computational Techniques for the Verification of Hybrid Systems], Claire J. Tomlin, Ian Mitchell, Alexandre M. Bayen, Meeko Oishi, Proceedings of the IEEE, Vol. 91, No. 7, July 2003.</ref>

==História==
Antes de a pesquisa propriamente dita explicitamente dedicada à complexidade dos problemas algorítmicos começar, os numerosos fundamentos foram estabelecidos por vários pesquisadores. O mais influente entre estes foi a definição das máquinas de Turing por Alan Turing em 1936, que acabou por ser uma noção muito robusta e flexível de computador.

{{Harvtxt|Fortnow|Homer|2003}} datam o início dos estudos sistemáticos em complexidade computacional com o importante artigo "On the Computational Complexity of Algorithms" de Juris Hartmanis e Richard Stearns (1965), que estabeleceu as definições de complexidade de tempo e de espaço e provou os teoremas de hierarquia.

De acordo com {{Harvtxt|Fortnow|Homer|2003}}, trabalhos anteriores que estudaram problemas solucionáveis por máquinas de Turing com recursos específicos limitados inclui a definição de John Myhill de [[Autômato linearmente limitado|autômatos linearmente limitados]] (Myhill 1960), o estudo de [[Raymond Smullyan]] sobre conjuntos rudimentares (1961), assim como o artigo de Hisao Yamada<ref>{{Citar periódico|titulo = Real-Time Computation and Recursive Functions Not Real-Time Computable|url = http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5219459|jornal = IRE Transactions on Electronic Computers|data = 1962-12-01|issn = 0367-9950|paginas = 753-760|volume = EC-11|numero = 6|doi = 10.1109/TEC.1962.5219459|primeiro = Hisao|ultimo = Yamada}}</ref> sobre computação em tempo real (1962). Um pouco mais cedo, [[Boris Trakhtenbrot]] (1956), um pioneiro no campo da URSS, estudou outra medida específica de complexidade.<ref>Trakhtenbrot, B.A.: Signalizing functions and tabular operators. Uchionnye Zapiski
Penzenskogo Pedinstituta (Transactions of the Penza Pedagogoical Institute) 4, 75–87 (1956) (in Russian)</ref> Como lembra ele:
{{quote|Contudo, [meu] interesse inicial [na teoria dos autômatos] era cada vez mais posto de lado em detrimento à complexidade computacional, uma excitante fusão de métodos combinatoriais, herdada da teoria da comutação, com o arsenal conceitual da teoria de algoritmos. Essas ideias me ocorreram antes, em 1955, quando eu cunhei o termo "função de sinalização", que hoje é comumente conhecido como "medida de complexidade".
|Boris Trakhtenbrot|From Logic to Theoretical Computer Science – An Update. In: ''Pillars of Computer Science'', LNCS 4800, Springer 2008.
}}

Em 1967, [[Manuel Blum]] desenvolveu uma teoria da complexidade axiomática com base em seus axiomas e provou um resultado importante, o então chamado, [[teorema da aceleração de Blum]] (speed-up theorem). O campo realmente começou a florescer quando o pesquisador norte-americano [[Stephen Cook]] e, trabalhando independentemente, [[Leonid Levin]] na URSS, provaram que existem importantes problemas praticáveis que são NP-completos. Em 1972, [[Richard Karp]] partiu desta ideia e deu um salto à frente com seu artigo histórico, "Reducibility Among Combinatorial Problems", no qual ele mostrou que 21 diferentes problemas de [[combinatória]] e problemas teóricos de grafos, famosos por sua intratabilidade computacional, são NP-completos.<ref>{{Citation |autor= Richard M. Karp |capítulo= Reducibility Among Combinatorial Problems |capítulourl= http://www.cs.berkeley.edu/~luca/cs172/karp.pdf |título= Complexity of Computer Computations | editor = R. E. Miller and J. W. Thatcher (editors) |publicado= New York: Plenum |páginas= 85–103 |ano= 1972}}</ref>

== Ver também ==
[[Imagem:Theoretical computer science.png|Theoretical computer science|700px|Relação entre teoria da computabilidade, teoria da complexidade e teoria da linguagem formal]]
*[[Problemas em aberto da ciência da computação]]
*[[:Categoria:Teoria da computação]]
*[[Lista de termos relacionados aos algoritmos e estruturas de dados]]

==Notas==
<references group="nb"/>

{{Referências|col=2}}

===Bibliografia===
*{{Citation|primeiro1=Sanjeev | authorlink1=Sanjeev Arora|último2=Barak |primeiro2=Boaz|título=Computational Complexity: A Modern Approach| url = http://www.cs.princeton.edu/theory/complexity/|publicado=[[Cambridge University Press|Cambridge]]|ano=2009| isbn=978-0-521-42426-4|autor=Sanjeev Arora, Boaz Barak }}
* {{Citation|último1=Downey|primeiro1=Rod|último2=Fellows|primeiro2=Michael| authorlink2=Michael Fellows|título=Parameterized complexity| url=http://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html?referer=www.springer.de%2Fcgi-bin%2Fsearch_book.pl%3Fisbn%3D0-387-94883-X|publicado=[[Springer-Verlag]]|local=Berlin, New York|ano=1999 }}
* {{citation|último=Du|primeiro=Ding-Zhu|autor2=Ko, Ker-I|título=Theory of Computational Complexity|publicado=[[John Wiley & Sons]]|ano=2000| local=US| isbn=978-0-471-34506-0 }}
* {{Citation|último=Goldreich|primeiro=Oded|autorlink=Oded Goldreich| url = http://www.wisdom.weizmann.ac.il/~oded/cc-book.html|título= Computational Complexity: A Conceptual Perspective|publicado= Cambridge University Press|ano= 2008 }}
* {{Citation|editor-sobrenome1=van Leeuwen|editor-nome1=Jan| editor1-link = Jan van Leeuwen|título=Handbook of theoretical computer science (vol. A): algorithms and complexity|publicado=[[MIT Press]]| isbn=978-0-444-88071-0|ano=1990 }}
* {{citation
 |último= Papadimitriou  |primeiro= Christos  |autorlink= Christos Papadimitriou  |título= Computational Complexity  |edição= 1st  |ano= 1994  |publicado= Addison Wesley  | isbn = 0201530821 }}
* {{Citation|último=Sipser|primeiro=Michael|autorlink=Michael Sipser|título=[[Introduction to the Theory of Computation]]|edição=2nd|ano=2006|publicado=[[Thomson Learning|Thomson Course Technology]]|local=USA|isbn=0534950973 }}
* {{Garey-Johnson}}

===Surveys===
* {{Citation |último1=Khalil |primeiro1=Hatem |último2=Ulery |primeiro2=Dana |autorlink2=Dana Ulery |título=A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations |publicado=ACM '76 Proceedings of the 1976 Annual Conference |ano=1976 |páginas=197 | url = http://portal.acm.org/citation.cfm?id=800191.805573 | doi=10.1145/800191.805573}}
* {{Citation |último1=Cook |primeiro1=Stephen |autorlink1=Stephen Cook |título=An overview of computational complexity |publicado=ACM |ano=1983 |periódico=Commun. ACM | issn=0001-0782 | volume=26 |número=6 |páginas=400–408 | doi=10.1145/358141.358144}}
* {{Citation |último1=Fortnow |primeiro1=Lance |último2=Homer |primeiro2=Steven |título=A Short History of Computational Complexity |ano=2003 |periódico=Bulletin of the EATCS | volume=80 |páginas=95–133 | url = http://people.cs.uchicago.edu/~fortnow/papers/history.pdf}}
* {{Citation |último1=Mertens |primeiro1=Stephan |título=Computational Complexity for Physicists |publicado=IEEE Educational Activities Department |local=Piscataway, NJ, USA |ano=2002 |periódico=Computing in Science and Engg. | issn=1521-9615 | volume=4 |número=3 |páginas=31–47 | doi=10.1109/5992.998639 | arxiv=cond-mat/0012185 }}

{{refend}}

==Ligações externas==
* [https://web.archive.org/web/20100726082118/http://qwiki.stanford.edu/wiki/Complexity_Zoo The Complexity Zoo]

[[Categoria:Complexidade]]
[[Categoria:Ciência da computação teórica]]