Complexidade computacional e o problema P vs NP / Computational complexity and the P vs NP problem

AUTOR(ES)

Igor Carboni Oliveira

DATA DE PUBLICAÇÃO

2010

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

ASSUNTO(S)

complexidade computacional diagonalização algoritmos computational complexity diagonalization algorithms

Documentos Relacionados

• Dinâmica simbiótica: o problema estratégico visto sob a perspectiva da complexidade
• Um estudo computacional sobre o problema de decomposiÃÃo de grafos em Ãrvore
• THE STEINER PROBLEM IN RECTILINEAR METRIC: PROPERTIES, NEW HEURISTICS AND COMPUTATIONAL STUDY
• HEURÍSTICAS PARA O PROBLEMA DAS P-MEDIANAS CONECTADAS
• ALGORITMOS PRIMAIS E DUAIS PARA O PROBLEMA DAS P-MEDIANAS