Teoremas de Hierarquia

Descrição:

Revisão rápida da última aula. Finalizado o teorema de Immerman-Szelepcsényi: NL = coNL. Foram introduzidos e provados os teoremas de hierarquia de tempo e espaço. Discutiu-se o uso dos teoremas de hierarquia para separar certas classes de complexidade.

Instrutor: Prof. Michael Sipser