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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
{{Определение
+
 
|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>
 
 
Опишем работу <tex>Verifier \ V</tex> и <tex>Prover \ P</tex> для класса <tex>\mathrm{IP}</tex>. <br><br>  
 
Опишем работу <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>V:\Sigma^* \times \Sigma^* \times \Sigma^* \to \Sigma^* \cup \{accept, reject\} </tex>. <br> <tex>V</tex> принимает на вход:  

Версия 20:42, 4 июня 2012

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

Опишем работу [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] следюущим образом:

  1. [math]j \le i \lt p, i[/math] — четное: [math]V(w,r,M_i)=m_{i+1}[/math];
  2. [math]j \le i \lt p, i[/math] — нечетное: [math]P(w,M_i)=m_{i+1}[/math];
  3. Последнее сообщение [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]