Defesa de Dissertação de Mestrado: André Willik Valenti
Document Actions
Defesa de Dissertação de Mestrado: Igor Carboni Oliveira
Complexidade Computacional e o Problema P vs NP.
| What | Defesa de Mestrado |
|---|---|
| When |
02/08/2010 from 10:00 to 12:00 |
| Where | Auditório do IC - Sala 85 - IC 2 |
| Add event to calendar |
vCal
iCal
|
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.
Concurso Público para Professor Doutor - MS-3
