Computação Probabilística, BPP

Descrição: Revisão rápida da última aula. Definidas máquinas de Turing probabilísticas e a classe BPP. Esboçado o lema de amplificação. Introduzidos programas de ramificação e programas de ramificação de leitura única. Iniciada a prova de que ROBP ∈ BPP. Introduzido o método de aritmetização.

Instrutor: Prof. Michael Sipser