BPP содержится в \( \Sigma_2^P \cap \Pi_2^P \). Интерактивные протоколы. Примеры: интерактивный протокол для неизоморфизма графов. Теорема Шамира (IP = PSPACE) и ее следствия.