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

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

Опишем работу Verifier \ V и Prover \ P для класса \mathrm{IP}.

V:\Sigma^* \times \Sigma^* \times \Sigma^* \to \Sigma^* \cup \{accept, reject\}.
V принимает на вход:

  1. Заданное слово.
  2. Некоторую рандомную строку. Для удобства мы предоставляем одну рандомную строку, вместо эквивалентной возможности делать вероятностные выборы в течении вычилений.
  3. Историю обмена сообщениями m_1*m_2*...*m_i с P.

На выход V выдает сообщение m_{i+1}accept, или reject, или следующее сообщение для P.

P:\Sigma^* \times \Sigma^* \to \Sigma^*.
P принимает на вход:

  1. Заданное слово.
  2. Историю обмена сообщениями m_1*m_2*...*m_i с V.

На выход P выдает следующее сообщение для Vm_{i+1}.

Определим взаимодействие между P и V.
Для заданного слова w и рандомной строки r будем писать V^P(w,r)=accept, если существует такая последовательность сообщений m_1...m_k для некоторого k, что:

  1. 0 \le i < k, i — четное: V(w,r,m_1*...*m_i)=m_{i+1};
  2. 0 < i < k, i — четное: P(w,m_1*...*m_i)=m_{i+1};
  3. Последнее сообщение m_kaccept.

Определение:
Pr[V^P accepts \ w]=Pr[V^P(w,r)=accept] , где w — заданное слово, r — рандомная строка.


Теорема:
\mathrm{IP} \subseteq \mathrm{PS}
Доказательство:
\triangleright

Рассмотрим какой-нибудь язык L из \mathrm{IP}. Предположим, что Verifier V обменивается ровно p сообщениями при входном слове w длины n. Мы сконструируем детерминированную машину Тьюринга M, симулирующую V. Введем определение: Pr[V \ accepts \ w]=\max\limits_{P} Pr[V^P accepts \ w]. Это значение не менее \frac{2}3, если w \in L, и не более \frac{1}3, если w \notin L. Покажем, как его вычислить, используя полиномиальный размер памяти.
За M_j будем обозначать историю сообщений m_1*...*m_j. Будем писать, что V^P(w,r,M_j) = accept, если мы можем продолжить M_j сообщениями m_{j+1}...m_p следюущим образом:

  1. j \le i < p,  i — четное: V(w,r,M_i)=m_{i+1};
  2. j \le i < p,  i — нечетное: P(w,M_i)=m_{i+1};
  3. Последнее сообщение m_p - accept.

Определим: Pr[V \ accepts \ w \ starting \ at \ M_j] = \max\limits_{P} Pr[V^P(w,r,M_j)=accept], где r — рандомная строка.
Для каждого 0 \le j \le p и каждого M_j определим функцию N_{M_j} следующим образом:
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},
где Pr_r для сообщения m_{j+1} означает вероятность получения такой рандомной строки r, что V(w,r,M_j)=m_{j+1}.
M_0 — пустая история сообщений. Докажем два утверждения относительно значения N_{M_0}. Во-первых, докажем, что N_{M_0} считается с использованием памяти полиномиального размера, во-вторых, что N_{m_0} = Pr[V \ accepts \ w].

  • Алгоритм вычисляет N_{M_j} для каждого j и M_j. Глубина рекурсии — p, а это, из определения класса \mathrm{IP}, полином от длины входа, поэтому и память для вычисления N_{M_j} нам нужна полиномиального размера .
  • Докажем, что для каждого 0 \le j \le p и каждого M_j выполняется: N_{M_j}=Pr[V \ accepts \ w \ starting \ at \ M_j].
\triangleleft
Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты