Связь классов IP и AM друг с другом и с другими классами языков

Эта статья находится в разработке!

Опишем работу [math]Verifier \ V[/math] и [math]Prover \ P[/math] для класса [math]\mathrm{IP}[/math].

[math]V:\Sigma^* \times \Sigma^* \times \Sigma^* \to \Sigma^* \cup \{accept, reject\} [/math].
[math]V[/math] принимает на вход:

1. Заданное слово.
2. Некоторую рандомную строку. Для удобства мы предоставляем одну рандомную строку, вместо эквивалентной возможности делать вероятностные выборы в течении вычилений.
3. Историю обмена сообщениями [math] m_1*m_2*...*m_i[/math] с [math]P[/math].

На выход [math]V[/math] выдает сообщение [math]m_{i+1}[/math] — [math]accept[/math], или [math]reject[/math], или следующее сообщение для [math]P[/math].

[math]P:\Sigma^* \times \Sigma^* \to \Sigma^* [/math].
[math]P[/math] принимает на вход:

1. Заданное слово.
2. Историю обмена сообщениями [math] m_1*m_2*...*m_i[/math] с [math]V[/math].

На выход [math]P[/math] выдает следующее сообщение для [math]V[/math] — [math]m_{i+1}[/math].

Определим взаимодействие между [math]P[/math] и [math]V[/math].
Для заданного слова [math]w[/math] и рандомной строки [math]r[/math] будем писать [math]V^P(w,r)=accept[/math], если существует такая последовательность сообщений [math]m_1...m_k[/math] для некоторого [math]k[/math], что:

1. [math]0 \le i \lt k[/math], [math]i[/math] — четное: [math]V(w,r,m_1*...*m_i)=m_{i+1}[/math];
2. [math]0 \lt i \lt k[/math], [math]i[/math] — четное: [math]P(w,m_1*...*m_i)=m_{i+1}[/math];
3. Последнее сообщение [math]m_k[/math] — [math]accept[/math].
   
   

Определение:

[math]Pr[V^P accepts \ w]=Pr[V^P(w,r)=accept][/math] , где [math]w[/math] — заданное слово, [math]r[/math] — рандомная строка.

Теорема:

[math]\mathrm{IP} \subseteq \mathrm{PS}[/math]

Доказательство:

[math]\triangleright[/math]

Рассмотрим какой-нибудь язык [math]L[/math] из [math]\mathrm{IP}[/math]. Предположим, что [math]Verifier[/math] [math]V[/math] обменивается ровно [math]p[/math] сообщениями при входном слове [math]w[/math] длины [math]n[/math]. Мы сконструируем детерминированную машину Тьюринга [math]M[/math], симулирующую [math]V[/math]. Введем определение: [math]Pr[V \ accepts \ w]=\max\limits_{P} Pr[V^P accepts \ w][/math]. Это значение не менее [math]\frac{2}3[/math], если [math]w \in L [/math], и не более [math]\frac{1}3[/math], если [math]w \notin L [/math]. Покажем, как его вычислить, используя полиномиальный размер памяти. За [math]M_j[/math] будем обозначать историю сообщений [math]m_1*...*m_j[/math]. Будем писать, что [math]V^P(w,r,M_j) = accept[/math], если мы можем продолжить [math]M_j[/math] сообщениями [math]m_{j+1}...m_p[/math] следюущим образом: [math]j \le i \lt p, i[/math] — четное: [math]V(w,r,M_i)=m_{i+1}[/math]; [math]j \le i \lt p, i[/math] — нечетное: [math]P(w,M_i)=m_{i+1}[/math]; Последнее сообщение [math]m_p - accept[/math]. Определим: [math]Pr[V \ accepts \ w \ starting \ at \ M_j] = \max\limits_{P} Pr[V^P(w,r,M_j)=accept][/math], где [math]r[/math] — рандомная строка. Для каждого [math]0 \le j \le p[/math] и каждого [math]M_j[/math] определим функцию [math]N_{M_j}[/math] следующим образом: [math]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 \lt 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 \lt p \ and \ j=2k,k \in \mathbb N\end{cases}[/math], где [math]Pr_r[/math] для сообщения [math]m_{j+1}[/math] означает вероятность получения такой рандомной строки [math]r[/math], что [math]V(w,r,M_j)=m_{j+1}[/math]. [math]M_0[/math] — пустая история сообщений. Докажем два утверждения относительно значения [math]N_{M_0}[/math]. Во-первых, докажем, что [math]N_{M_0}[/math] считается с использованием памяти полиномиального размера, во-вторых, что [math]N_{m_0} = Pr[V \ accepts \ w][/math]. Алгоритм вычисляет [math]N_{M_j}[/math] для каждого [math]j[/math] и [math]M_j[/math]. Глубина рекурсии — [math]p[/math], а это, из определения класса [math]\mathrm{IP}[/math], полином от длины входа, поэтому и память для вычисления [math]N_{M_j}[/math] нам нужна полиномиального размера . Докажем, что для каждого [math]0 \le j \le p[/math] и каждого [math]M_j[/math] выполняется: [math]N_{M_j}=Pr[V \ accepts \ w \ starting \ at \ M_j][/math].

[math]\triangleleft[/math]