A área de complexidade computacional estuda quantos recursos computacionals (e.g. tempo, memória) é que um algoritmo necessita para resolver um dado problema. Por exemplo:

• Quantas operações lógicas são necessárias para multiplicar dois números x e y, ambos com n casas decimais?
• Quantas multiplicações são necessárias para multiplicar duas matrizes reais A e B de n×n?
• Quanto tempo precisa um algoritmo para determinar o caminho mais curto entre dois pontos de um mapa?
• Quanto tempo precisa para determinar se um sistema de equações lineares com n variáveis tem uma solução em ℝⁿ?
• Quanto tempo precisa para obter a factorização prima de um dado um número inteiro?
• Quanto tempo precisa para determinar se um sistema de inequações lineares com n variáveis tem uma solução em ℤⁿ?
• Se alguém nos diz saber demonstrar um dado teorema, quantas perguntas temos de fazer para ficarmos convencidos, com 99% de certeza, que de facto o teorema é verdadeiro e a pessoa conhece uma demonstração dele?

Nesta palestra vou dar uma introdução informal à complexidade computacional, e explicar informalmente alguns problemas e resultados fundamentais da área.