Изменения
Новая страница: «{{В разработке}} {{Определение |definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex> }} {{Определе...»
{{В разработке}}
{{Определение
|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>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> {{---}} рандомная строка длины <tex>p</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>Pr_r</tex> для сообщения <tex>m_{j+1}</tex> означает вероятность взятия такой рандомной строки <tex>r</tex> длины <tex>p</tex>, что <tex>V(w,r,M_j)=m_{j+1}</tex>.
}}
{{Определение
|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>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> {{---}} рандомная строка длины <tex>p</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>Pr_r</tex> для сообщения <tex>m_{j+1}</tex> означает вероятность взятия такой рандомной строки <tex>r</tex> длины <tex>p</tex>, что <tex>V(w,r,M_j)=m_{j+1}</tex>.
}}
