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 thumb|upright=1.5|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 thumb|upright=0.6|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 tais que a relação é 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 vértices em comparação com o tempo gasto para um grafo com vértices?

Se o tamanho da entrada é , o tempo gasto pode ser expresso como uma função de . Como o tempo gasto em diferentes entradas do mesmo tamanho pode ser diferente, a complexidade de tempo de pior caso é definida como o tempo máximo gasto em todas as entradas de tamanho . Se é um polinômio em , 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

thumb|right|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.Ver O que todos esses modelos têm em comum é que as máquinas operam de forma determinística.