Revisão rápida da última aula. Definiu as classes de complexidade NTIME e a classe NP. Mostrou ∈ NP. Discutiu a questão P versus NP. Provou CFG ∈ P. Introduziu o problema de satisfabilidade e a redutibilidade em tempo polinomial.

Instrutor: Prof. Michael Sipser

Não há vídeo para a Palestra 13, pois esse foi o dia do Exame Intermediário.