Что такое недетерминированные и вероятностные вычисления: различные подходы. Класс NP и примеры задач из него. Определения вероятностных классов и простейшие соотношения. Другие недетерминированные сложностные классы и соотношения между ними. Обзор известных результатов о проблемах равенства классов.