Вероятностные машины Тьюринга. Классы BPP и RP. Лемма Шварца-Зиппеля. Тестирование равенства полиномов. Проверка на равенство однопроходных ветвящихся программ. Теорема Адлемана. Теорема Сипсера-Гача.