Complexidade computacional e o problema P vs NP

Autor(es)

Igor Carboni Oliveira

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2010-02-08

Membros da banca

Arnaldo Vieira Moura; José Coelho de Pina Junior; Flávio Keidi Miyazawa

• Orientador: Arnaldo Vieira Moura

Resumo

A teoria de complexidade computacional procura estabelecer limites para a eficiência dos algoritmos, 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. Os principais resultados obtidos por diagonalização são os teoremas de hierarquia de tempo e de espaço (Hartmanis e Stearns [54, 104]). Apresentamos uma generalização desses resultados, 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 (AU)

• Processo FAPESP: 08/07040-0 - Complexidade Computacional e o Problema P vs NP
• Beneficiário: Igor Carboni Oliveira
• Modalidade de apoio: Bolsas no Brasil - Mestrado