Resolver ou verificar?
Celina M. H. de Figueiredo (COPPE/UFRJ)

Resolver ou verificar? é uma pergunta que vale um milhão de dólares. No ano 2000, o Instituto Clay para Matemática distinguiu sete problemas considerados centrais para o progresso da matemática, chamando-os de Os Problemas do Milênio. A solução de cada problema corresponde a um prêmio de um milhão de dólares. Um dos sete problemas selecionados é um problema de teoria da computação: existe pergunta cuja resposta pode ser verificada rapidamente mas cuja resposta requer muito tempo para ser encontrada? Esse problema do milênio, conhecido como P versus NP, é o problema central na área de complexidade computacional, onde tentamos classificar a dificuldade dos problemas de acordo com a eficiência das possíveis soluções através de algoritmos computacionais.