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,...