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 é primo ou não. As instâncias deste problema são 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 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 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 thumb|200px|Um caminho ótimo para o caixeiro viajante passando pelas 15 maiores cidades da Alemanha. É o menor caminho entre as 43.589.145.600Escolha 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. 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 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 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úmeros inteiros podem ser representados em notação binária, e grafos podem ser codificados diretamente via suas matrizes de adjacência, ou por codificação de suas 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.
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 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 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 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, b, c) tal qual a relação a × b = 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 2n 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 thumb|Uma representação artística de uma 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 de Conway, 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 classes de complexidade, tais 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 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 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