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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}} {{Определение |definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex> }} {{Определе...»)
 
Строка 9: Строка 9:
 
Опишем работу <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> принимает на вход:  
# Заданное слово;
+
# Заданное слово.
# Некоторую рандомную строку;
+
# Некоторую рандомную строку. Для удобства мы предоставляем одну рандомную строку, вместо эквивалентной возможности делать вероятностные выборы в течении вычилений.
 
# Историю обмена сообщениями <tex> m_1*m_2*...*m_i</tex> с <tex>P</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>.
 
На выход <tex>V</tex> выдает сообщение <tex>m_{i+1}</tex> {{---}} <tex>accept</tex>, или <tex>reject</tex>, или следующее сообщение для <tex>P</tex>.
 
<br><br>
 
<br><br>
 
<tex>P:\Sigma^* \times \Sigma^* \to \Sigma^* </tex>.<br> <tex>P</tex> принимает на вход:
 
<tex>P:\Sigma^* \times \Sigma^* \to \Sigma^* </tex>.<br> <tex>P</tex> принимает на вход:
#Заданное слово;
+
#Заданное слово.
 
#Историю обмена сообщениями <tex> m_1*m_2*...*m_i</tex> с <tex>V</tex>.
 
#Историю обмена сообщениями <tex> m_1*m_2*...*m_i</tex> с <tex>V</tex>.
 
На выход <tex>P</tex> выдает следующее сообщение для <tex>V</tex>  {{---}} <tex>m_{i+1}</tex>.
 
На выход <tex>P</tex> выдает следующее сообщение для <tex>V</tex>  {{---}} <tex>m_{i+1}</tex>.
 
<br><br>
 
<br><br>
 
Определим взаимодействие между <tex>P</tex> и <tex>V</tex>. <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>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 \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>0 < i < k</tex>, <tex>i</tex> {{---}} четное: <tex>P(w,m_1*...*m_i)=m_{i+1}</tex>;
Строка 33: Строка 33:
 
Рассмотрим какой-нибудь язык <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>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>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>\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>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>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>j \le i < p,  i</tex> {{---}} нечетное: <tex>P(w,M_i)=m_{i+1}</tex>;
 
#Последнее сообщение <tex>m_p - accept</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> {{---}} рандомная строка длины <tex>p</tex>.<br>
+
Определим: <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>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>,
+
<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>p</tex>, что <tex>V(w,r,M_j)=m_{j+1}</tex>.
+
где <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> нам нужна полиномиального размера .
 
}}
 
}}

Версия 00:56, 4 июня 2012

Эта статья находится в разработке!
Определение:
[math]\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] [/math]


Определение:
[math]\mathrm{AM}=\bigcup\limits_{p(n) \in poly} \mathrm{AM} [p(n)] [/math]


Опишем работу [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]\triangleleft[/math]