Olá. Imagino que o texto da tese esteja disponível eletronicamente. Gostaria de ler.
Abraços, obrigado pela divulgação, Carlos Camarão > 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 > _______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
