Изменения
Нет описания правки
<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>.
}}
