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