210
правок
Изменения
м
Нет описания правки
{{Определение
|definition =
<b>Интерактивным протоколом</b> <tex> \langle P, V \rangle </tex>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок) , моделирующая вычисления как обмен сообщениями между двумя программами (где <tex>P</tex> означает <tex> \mathit{Prover}</tex> и <tex> V </tex> означает <tex>\mathit{Verifier}</tex>), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен по времени вычисления и памяти;
