Изменения

<b>Интерактивным протоколом</b>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (Prover и Verifier, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что

# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;

# <tex>V</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;

# <tex>V</tex> — вероятностная машина Тьюринга;

# <tex>V</tex> ограничен полиномиальным временем работы.