Busca avançada
Ano de início
Entree


Complexidade computacional e o problema P vs NP

Texto completo
Autor(es):
Igor Carboni Oliveira
Número total de Autores: 1
Tipo de documento: Dissertação de Mestrado
Imprenta: Campinas, SP.
Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
Data de defesa:
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