40
правок
Изменения
Нет описания правки
|proof=
Будем использовать следующий протокол:
# <tex>V</tex> возьмёт случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>π\pi</tex> с вероятностной ленты; <br/># <tex>V</tex> создаст новый граф, перемешав вершины графа номер <tex>i</tex> перестановкой <tex>π\pi</tex>; <br/>
# <tex>V</tex> перешлёт <tex>P</tex> полученный граф с вопросом, из какого из исходных графов он был получен; <br/>
# <tex>V</tex> получив ответ, сравнит его с правильным ответом — числом <tex>i</tex>.
}}
