A Prof. Celina Figueiredo (COPPE/UFRJ) abriu o III Workshop da Escola de Informática e Computação com a palestra intitulada “Resolver ou Verificar?”
Resumo:
“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. Discutiremos o problema P versus NP, através da classificação de problemas desafiadores em polinomial ou NP-completo e na definição de classes de problemas que admitem um resultado de dicotomia, onde cada problema da classe é classificado como polinomial ou NP-completo.
