Просмотр исходного текста страницы Связь классов IP и AM друг с другом и с другими классами языков

{{В разработке}}

Опишем работу <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_1*m_2*...*m_i</tex> с <tex>P</tex>.
На выход <tex>V</tex> выдает сообщение <tex>m_{i+1}</tex> {{---}} <tex>accept</tex>, или <tex>reject</tex>, или следующее сообщение для <tex>P</tex>.
<br><br>
<tex>P:\Sigma^* \times \Sigma^* \to \Sigma^* </tex>.<br> <tex>P</tex> принимает на вход:
#Заданное слово.
#Историю обмена сообщениями <tex> m_1*m_2*...*m_i</tex> с <tex>V</tex>.
На выход <tex>P</tex> выдает следующее сообщение для <tex>V</tex>  {{---}} <tex>m_{i+1}</tex>.
<br><br>
Определим взаимодействие между <tex>P</tex> и <tex>V</tex>. <br>
Для заданного слова <tex>w</tex> и рандомной строки <tex>r</tex> будем писать <tex>V^P(w,r)=accept</tex>, если существует такая последовательность сообщений <tex>m_1...m_k</tex> для некоторого <tex>k</tex>, что:
#<tex>0 \le i < k</tex>, <tex>i</tex> {{---}} четное: <tex>V(w,r,m_1*...*m_i)=m_{i+1}</tex>;
#<tex>0 < i < k</tex>, <tex>i</tex> {{---}} четное: <tex>P(w,m_1*...*m_i)=m_{i+1}</tex>;
#Последнее сообщение <tex>m_k</tex> {{---}} <tex>accept</tex>.<br><br>
{{Определение
|definition = <tex>Pr[V^P accepts \ w]=Pr[V^P(w,r)=accept]</tex> , где <tex>w</tex> {{---}} заданное слово, <tex>r</tex> {{---}} рандомная строка.
}}
<br>
{{Теорема
|statement=<tex>\mathrm{IP} \subseteq \mathrm{PS}</tex>
|proof=
Рассмотрим какой-нибудь язык <tex>L</tex> из <tex>\mathrm{IP}</tex>.  Предположим,  что <tex>Verifier</tex> <tex>V</tex> обменивается ровно <tex>p</tex> сообщениями при входном слове <tex>w</tex> длины <tex>n</tex>. Мы сконструируем детерминированную машину Тьюринга <tex>M</tex>, симулирующую <tex>V</tex>.
Введем определение:  
<tex>Pr[V \ accepts \ w]=\max\limits_{P} Pr[V^P accepts \ w]</tex>. 
Это значение не менее <tex>\frac{2}3</tex>, если <tex>w \in L </tex>, и не  более <tex>\frac{1}3</tex>, если <tex>w \notin L </tex>. Покажем, как его вычислить, используя полиномиальный размер памяти.<br>
За <tex>M_j</tex> будем обозначать историю сообщений <tex>m_1*...*m_j</tex>. Будем писать, что <tex>V^P(w,r,M_j) = accept</tex>, если мы можем продолжить <tex>M_j</tex> сообщениями <tex>m_{j+1}...m_p</tex> следюущим образом:
#<tex>j \le i < p,  i</tex> {{---}} четное: <tex>V(w,r,M_i)=m_{i+1}</tex>;
#<tex>j \le i < p,  i</tex> {{---}} нечетное: <tex>P(w,M_i)=m_{i+1}</tex>;
#Последнее сообщение <tex>m_p - accept</tex>.
Определим: <tex>Pr[V \ accepts \ w \ starting \ at \ M_j] = \max\limits_{P} Pr[V^P(w,r,M_j)=accept]</tex>, где <tex>r</tex> {{---}} рандомная строка.<br>
Для каждого <tex>0 \le j \le p</tex> и каждого <tex>M_j</tex> определим функцию <tex>N_{M_j}</tex> следующим образом:<br>
<tex>N_{M_j}=\begin{cases}0 ,&j=p \ and \ m_p=reject\\1,&j=p \ and \ m_p=accept\\ max_{m_{j+1}}N_{M_{j+1}},&  j < p \ and \ j=2k+1,k \in \mathbb N\\\sum\limits_{m_{j+1}}(Pr_r[V(w,r,M_j)=m_{j+1}]\cdot N_{M_{j+1}}),&  j < p \ and \ j=2k,k \in \mathbb N\end{cases}</tex>, <br>
где <tex>Pr_r</tex> для сообщения <tex>m_{j+1}</tex> означает вероятность получения такой рандомной строки <tex>r</tex>, что <tex>V(w,r,M_j)=m_{j+1}</tex>.<br>
<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>.
}}