Интерактивные протоколы. Примеры: интерактивный протокол для неизоморфизма графов и для квадратичных невычетов. Теорема Шамира (IP = PSPACE) и ее следствия.