40
правок
Изменения
Нет описания правки
|statement=<tex>GNI \in \mathrm{IP[1]}</tex>
|proof=
Будем использовать следующий протокол действий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; <br/>
# Создадим новый граф, перемешав вершины графа номер <tex>i</tex> перестановкой <tex>\pi</tex>; <br/>
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.
Покажем, что такой протокол это удовлетворяет ограничениям на IP[1].
Во-первых, очевидно, что число раундов не превосходит трёх.
Рассмотрим теперь случаи
