40
правок
Изменения
Нет описания правки
|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> не ограничен в вычислительной мощности;
# <tex>V</tex> — вероятностная машина Тьюринга;
