Caros Colegas: gostaria de divulgar a defesa de Dissertação de Mestrado de Igor Carboni Oliveira. Embora não se trate de meu orientando, nem eu esteja na Banca, Igor estudou comigo durante dois anos (Iniciação Científica) e o que trabalhamos, Lógica e Computabilidade, ajudou a moldar seu trabalho.
Att., Walter Carnielli ---------------------------------------- Universidade Estadual de Campinas - UNICAMP Instituto de Computação - IC D E F E S A D E DISSERTAÇÃO DE MESTRADO Segunda-feira, 02/08/2010 às 10h Sala: Auditório do IC sala 85 (IC-02 ) Titulo: Complexidade Computacional e o Problema P vs NP Nome do aluno: Igor Carboni Oliveira Banca Examinadora Prof. Dr. Arnaldo Vieira Moura (Orientador) -- IC / UNICAMP Prof. Dr. José Coelho de Pina - IME / USP Prof. Dr. Flávio Keidi Miyazawa - IC / UNICAMP Prof. Dr. Julio C. López Hernández (Suplente) -- IC / UNICAMP Profa. Dra. Ana Cristina Vieira de Melo (Suplente) - IME / USP RESUMO A teoria de complexidade computacional procura estabelecer limites para o universo algorítmico, investigando a dificuldade inerente dos problemas computacionais. O problema P vs NP é uma questão central em complexidade computacional. Informalmente, ele procura determinar se, para uma classe importante de problemas computacionais, a busca exaustiva por soluções é essencialmente a melhor alternativa algorítmica possível. Esta dissertação oferece tanto uma introdução clássica ao tema, quanto uma exposição a diversos teoremas mais avançados, resultados recentes e problemas em aberto. Em particular, o método da diagonalização é discutido em profundidade. Embora a diagonalização seja uma técnica clássica em complexidade computacional, esse é o único método conhecido capaz de separar certas classes de complexidade importantes. Os principais resultados obtidos por diagonalização são os teoremas de hierarquia (Hartmanis e Stearns). Intuitivamente, esses resultados estabelecem que, com mais recursos, é possível resolver mais problemas computacionais. Apresentamos uma generalização dos teoremas de hierarquia determinísticos, obtendo como corolários os teoremas clássicos provados por Hartmanis e Stearns. Essa é a primeira vez que uma prova unificada desses resultados aparece na literatura. ---------------------------------------- -- +++++++++++++++++++++++++++++++++++++++++++++++++ Walter Carnielli Centre for Logic, Epistemology and the History of Science – CLE State University of Campinas –UNICAMP P.O. Box 6133 13083-970 Campinas -SP, Brazil Phone: (+55) (19) 3521-6515 Fax: (+55) (19) 3289-3269 e-mail: [email protected] Website: http://www.cle.unicamp.br/prof/carnielli _______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
