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