O Problema do Milênio sobre Intratabilidade Computacional 

A palestra “O Problema do Milênio sobre Intratabilidade Computacional”, apresentada por Celina Miraglia Herrera de Figueiredo, trata do famoso problema P versus NP, um dos sete Problemas do Milênio propostos pelo Clay Mathematics Institute no ano 2000. A questão central do problema é saber se todo problema cuja solução pode ser verificada rapidamente por um algoritmo (classe NP) também pode ser resolvido rapidamente (classe P). Em termos práticos, isso significa investigar se verificar uma resposta correta é tão difícil quanto encontrar essa resposta.

O problema P vs NP tem implicações profundas tanto na matemática quanto na ciência da computação. Exemplos clássicos incluem problemas de grafos como o Caminho Hamiltoniano, em que é fácil conferir se um caminho é válido, mas extremamente difícil encontrar esse caminho. A discussão sobre a dificuldade computacional remonta a ideias formuladas por grandes pensadores como Hilbert, Gödel, Turing e von Neumann, sendo que já nos anos 1930 e 1950, conceitos como indecidibilidade e complexidade começaram a ser explorados.

Ao longo da palestra, são apresentados os principais pesquisadores e suas contribuições para a área, como Stephen Cook, que mostrou em 1971 que o problema de satisfatibilidade (SAT) é NP-completo, e Richard Karp, que em 1972 demonstrou que vários problemas combinatórios clássicos são equivalentes ao SAT em termos de dificuldade. Também são abordadas distinções conceituais como NP-completo e NP-difícil, sendo estas fundamentais para a teoria da complexidade.

Outro tema importante discutido é o uso da aleatoriedade em algoritmos. Avi Wigderson, ganhador dos prêmios Abel e Turing, contribuiu significativamente para a compreensão do papel da aleatoriedade na computação, mostrando que sob certas condições problemas randomizados podem ser simulados de forma determinística. Essa ideia, conhecida como "troca entre dificuldade e aleatoriedade", revela uma conexão profunda entre a existência de problemas difíceis e a possibilidade de eliminar o uso do acaso nos algoritmos.

A palestra também aborda a importância da matemática discreta na ciência da computação, destacando a combinatória como ferramenta essencial para o projeto e análise de algoritmos. A obra “Computers and Intractability: A Guide to the Theory of NP-Completeness”, de Garey e Johnson, é mencionada como um marco fundamental na área.

Obteve bacharelado (1982) e mestrado (1984) em Matemática na PUC-Rio, mestrado (1987) em Matemática no UMIST (UK), doutorado (1991) em Engenharia de Sistemas e Computação na COPPE/UFRJ com período sanduíche na University of Waterloo, Canadá. Fez carreira docente na UFRJ, onde ingressou no Instituto de Matemática em 1989, e na COPPE em 1991. Fez pós-doutorado em 1995 na University of Waterloo, Canadá. Desde 2011, é professora titular do Programa de Engenharia de Sistemas e Computação da COPPE, onde coordena o Núcleo de Excelência em Algoritmos Randomizados, Quânticos, e Aproximativos: Projeto, Análise e Implementação de Soluções Eficientes para problemas Combinatórios Fundamentais. É pesquisadora na área de Ciência da Computação, com ênfase em Teoria da Computação, e lidera o grupo de algoritmos e combinatória da COPPE, atuando principalmente nos seguintes temas: teoria dos grafos, algoritmos e complexidade computacional. Tem bolsa de produtividade em pesquisa do CNPq desde 1992, estando desde 2012 no nível 1A. É desde 2005 Cientista do Nosso Estado FAPERJ. Recebeu em 2006 o Prêmio Giulio Massarani de Mérito Acadêmico da COPPE. Recebeu em 2013 homenagem na solenidade comemorativa dos 50 anos da COPPE. Foi eleita em 2022 membra titular da Academia Brasileira de Ciências