1632
правки
Изменения
м
{{Определение|definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex>}}{{Определение|definition = <tex>\mathrm{AM}=\bigcup\limits_{p(n) \in poly} \mathrm{AM} [p(n)] </tex>}}<br>
rollbackEdits.php mass rollback
{{В разработке}}
Опишем работу <tex>Verifier \ V</tex> и <tex>Prover \ P</tex> для класса <tex>\mathrm{IP}</tex>. <br><br>
<tex>V:\Sigma^* \times \Sigma^* \times \Sigma^* \to \Sigma^* \cup \{accept, reject\} </tex>. <br> <tex>V</tex> принимает на вход:
<tex>M_0</tex> {{---}} пустая история сообщений. Докажем два утверждения относительно значения <tex>N_{M_0}</tex>. Во-первых, докажем, что <tex>N_{M_0}</tex> считается с использованием памяти полиномиального размера, во-вторых, что <tex>N_{m_0} = Pr[V \ accepts \ w]</tex>.
*Алгоритм вычисляет <tex>N_{M_j}</tex> для каждого <tex>j</tex> и <tex>M_j</tex>. Глубина рекурсии {{---}} <tex>p</tex>, а это, из определения класса <tex>\mathrm{IP}</tex>, полином от длины входа, поэтому и память для вычисления <tex>N_{M_j}</tex> нам нужна полиномиального размера .
*Докажем, что для каждого <tex>0 \le j \le p</tex> и каждого <tex>M_j</tex> выполняется: <tex>N_{M_j}=Pr[V \ accepts \ w \ starting \ at \ M_j]</tex>.
}}
