Бюрократы, editor, Администраторы
422
правки
Изменения
→Класс IP
{{Определение
|definition =
<b>Интерактивным протоколом</b>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> неограничен не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin GNI</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Так как может быть до двух раундов протокола, вероятность Вероятность того, что <tex>V</tex> примет слово <tex>x</tex> , когда оно не принадлежит языку (т.е. то есть <tex>P</tex> два раза пройдёт проверки <tex>V</tex>подряд верно угадает номер графа) , равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}
