Эта статья находится в разработке!
Опишем работу [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] принимает на вход:
- Заданное слово.
- Некоторую рандомную строку. Для удобства мы предоставляем одну рандомную строку, вместо эквивалентной возможности делать вероятностные выборы в течении вычилений.
- Историю обмена сообщениями [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] принимает на вход:
- Заданное слово.
- Историю обмена сообщениями [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], что:
- [math]0 \le i \lt k[/math], [math]i[/math] — четное: [math]V(w,r,m_1*...*m_i)=m_{i+1}[/math];
- [math]0 \lt i \lt k[/math], [math]i[/math] — четное: [math]P(w,m_1*...*m_i)=m_{i+1}[/math];
- Последнее сообщение [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] |
