Интерактивные системы доказательств
Пусть А и В
- две интерактивные, т. е. взаимодействующие через общую коммуникационную ленту, вероятностные машины Тьюринга. Через [В(х),А(х)] обозначается случайная величина - выходное слово машины А, когда А и В работают на входном слове х. Через |х| обозначается длина слова х.
Интерактивным доказательством для языка L называется пара интерактивных машин Тьюринга (P,V) такая, что выполняются следующие два условия.
1. (Полнота). Для всех хÎL вероятность Prob{[P(x),V(x)]=1}=1.
2. (Корректность). Для любой машины Тьюринга Р*, для любого полинома р и для всех хÎL достаточно большой длины Prob{[P*(x),V(x)]=1}<l/p(|x|).
Формальные определения интерактивных систем доказательств и интерактивных систем доказательств с нулевым разглашением даны в приложении.
