Изменения
→Определение
==Определение==
'''Интерактивный протокол доказательства''' - абстрактная машина, модулирующая вычисление как передачу сообщений между двумя частямисущностями: <tex>P</tex> - prover и <tex>V</tex> - verifier. В ходе данного взаимодействия <tex>P</tex> и <tex>V</tex> определяют, принадлежит ли данное слово <tex>x</tex> языку. <tex>P</tex> имеет неограниченную вычислительную мощность и пытается доказать, что <tex>x</tex> принадлежит языку. <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]],
работающая за полином и проверяющая информацию от <tex>P</tex>. При этом <tex>P</tex> не видит вероятностную ленту <tex>V</tex>. <tex>V</tex> хочет допустить слово тогда, и только тогда, когда оно принадлежит языку.
