Problemas Comprovadamente Intratáveis, Oráculos

Descrição:

Revisão rápida da última aula. Foram introduzidas classes de complexidade exponencial e demonstrado um problema "natural" comprovadamente intratável. Apresentados oráculos e computação relativizada para sugerir que métodos baseados puramente em diagonalização não são suficientes para separar P de NP.Instrutor: Prof. Michael Sipser