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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
{{В разработке}}
 
{{В разработке}}
  

Текущая версия на 19:07, 4 сентября 2022

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

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