Викиконспекты - Вклад участника [ru]

Теорема о соотношении coNP и IP

2012-06-05T13:40:22Z

Байдаров Андрей:

{{Определение
|definition=
<tex>\mathrm{\#SAT}=\{\langle \varphi, k \rangle \bigm| \varphi</tex> имеет ровно <tex>k</tex> удовлетворяющих наборов <tex>\}</tex>.
}}

{{Лемма
|about=1
|statement=<tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\phi(x_1, \ldots, x_m)=k \Leftrightarrow \langle\phi,k\rangle \in \mathrm{\#SAT}</tex>.
|proof=Следует из [[Арифметизация булевых формул с кванторами | леммы (1)]].
}}

{{Лемма
|about=2
|statement=<tex>\mathrm{\#SAT} \in \mathrm{IP}</tex>.
|proof=
Для доказательства леммы построим программы <tex>\mathit{Verifier}</tex> и <tex>\mathit{Prover}</tex> из [[Интерактивные протоколы. Класс IP. Класс AM#Класс IP|определения]] класса <tex>\mathrm{IP}</tex>.

Сперва арифметизуем формулу <tex>\phi</tex>. Пусть полученный полином <tex>A(x_1, x_2, ..., x_m)</tex> имеет степень <tex>d</tex>.

По лемме (1) вместо условия <tex>\langle \phi, k \rangle \in \mathrm{\#SAT}</tex>, можно проверять условие <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\phi(x_1, \ldots, x_m)=k</tex>.

Приступим к описанию <tex>\mathit{Verifier}</tex>'а.

'''Шаг 0'''

Если <tex>d=0</tex> или <tex>m=0</tex>, то <tex>\mathit{Verifier}</tex> может проверить указанное выше условие сам и вернуть соответствующий результат.
Иначе запросим у <tex>\mathit{Prover}</tex>'а такое простое число <tex>p</tex>, что <tex>3dm \le p \le 6dm</tex> (такое <tex>p</tex> существует в силу [http://ru.wikipedia.org/wiki/Постулат_Бертрана постулата Бертрана]).
Проверим <tex>p</tex> на простоту и на принадлежность заданному промежутку. Как мы [[Класс P#Примеры задач и языков из P|знаем]], <tex>\mathrm{Primes} \in \mathrm{P}</tex>, следовательно на эти операции у <tex>\mathit{Verifier}</tex>'а уйдёт полиномиальное от размера входа время.

Далее будем проводить все вычисления модулю <tex>p</tex>.

Попросим <tex>\mathit{Prover}</tex> 'а прислать <tex>\mathit{Verifier}</tex>'у формулу <tex>A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(x_1, x_2, ..., x_m)</tex>.
Заметим, что размер формулы <tex>A_0(x_1)</tex> будет полином от длины входа <tex>\mathit{Verifier}</tex> 'а, так как <tex>A_0(x_1)</tex> — полином степени не выше, чем <tex>d</tex>, от одной переменной, а значит его можно представить в виде <tex>A_0(x) = \sum\limits_{i = 0}^{d} C_i \cdot x ^ i</tex>.

Проверим следующее утверждение: <tex>A_0(0) + A_0(1) = k</tex> (*) (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, <tex>\mathit{Verifier}</tex> продолжает свою работу, иначе он прекращает свою работу и возвращет '''false''').

'''Шаг i'''

Пусть <tex>r_i = random(0..p-1)</tex>. Отправим <tex>r_i</tex> программе <tex>\mathit{Prover}</tex>.

Попросим <tex>\mathit{Prover}</tex> 'а прислать <tex>\mathit{Verifier}</tex>'у формулу <tex>A_i(x_{i+1}) = \sum\limits_{x_{i+2} = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(r_1,\ldots, r_i, x_{i+1}, ..., x_m)</tex>.

Проверим следующее утверждение: <tex>A_i(0) + A_i(1) = A_{i-1}(r_i)</tex> (*).

'''Шаг m'''

Пусть <tex>r_m = random(0..p-1)</tex>. Отправим <tex>r_m</tex> программе <tex>\mathit{Prover}</tex>.

Попросим программу <tex>\mathit{Prover}</tex> прислать <tex>\mathit{Verifier}</tex>'у значение <tex>A_m()= A(r_1, r_2, ..., r_m)</tex>.

Проверим следующее утверждение: <tex>A_m() = A_{m-1}(r_m)</tex> (*).
А также сами подставим <tex>r_1, r_2, ..., r_m</tex> в <tex>A(x_1, x_2, ..., x_m)</tex> и проверим правильность присланного значения <tex>A_m()</tex>.

Возвращаем '''true'''.

Докажем теперь, что построенный таким образом <tex>\mathit{Verifier}</tex> — корректный. Для этого нужно доказать следующие утверждения:
# Построенный <tex>\mathit{Verifier}</tex> - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
# <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT} \Rightarrow \exists \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \ge 2/3</tex>.
# <tex>\langle \varphi, k \rangle \notin \mathrm{\#SAT} \Rightarrow \forall \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le 1/3</tex>.

Докажем эти утверждения.

#Первый факт следует из построения <tex>\mathit{Verifier}</tex> 'а.
#По [[Арифметизация булевых формул с кванторами | лемме (2)]], если <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\phi(x_1, \ldots, x_m)=k</tex>, то условия (*) выполнятются, следовательно существует такой <tex>\mathit{Prover}</tex>, что <tex>P(\mathit{Verifier^{Prover}}(\langle\phi,k\rangle)) = 1</tex>, для любой пары <tex>\langle\phi,k\rangle \in \mathrm{\#SAT}</tex>.
#Пусть количество наборов, удовлетворяющих <tex>\phi</tex>, не равно <tex>k</tex>. Для того, что бы <tex>\mathit{Verifier}</tex> вернул '''true''', <tex>\mathit{Prover}</tex> 'у необходимо посылать такие <tex>A_i</tex>, чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
:'''Шаг 0'''
:Так как количество наборов, удовлетворяющих <tex>\phi</tex>, не равно <tex>k</tex>, то <tex>\mathit{Prover}</tex> не может послать правильное <tex>A_0</tex>, поскольку в этом случае не выполнится условие <tex>A_0(0) + A_0(1) = k</tex>. Поэтому он посылает не <tex>A_0</tex>, а некое <tex>\tilde{A}_0</tex>.
:<tex>\ldots</tex>
:'''Шаг i'''
:Заметим, что если на каком-то шаге <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то начиная со следующего шага <tex>\mathit{Prover}</tex> может посылать правильные <tex>A_j</tex> и в итоге <tex>\mathit{Verifier}</tex> вернёт '''true'''.
:Для некоторого случайно выбранного <tex>r_i</tex> вероятность того, что <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то есть <tex>r_i</tex> — корень полинома <tex>(A_{i-1} - \tilde{A}_{i-1})(r_i)</tex>, имеющего степень не больше <tex>d</tex>, не превосходит <tex>\frac{d}{p}</tex>.
:<tex>\ldots</tex>
:'''Шаг m'''
:Так как на последнем шаге <tex>\mathit{Verifier}</tex> сверяет полученное от <tex>\mathit{Prover}</tex>'а значение с непосредственно вычисленным, слово будет допущено только в том случае, когда <tex>\mathit{Prover}</tex> смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
:
:Вычислим вероятность того, что хотя бы раз корень был угадан.
:<tex>P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m \le \frac 1 3</tex>.
:В последнем переходе мы воспользовались [http://ru.wikipedia.org/wiki/Ряд_Тейлора формулой Тейлора] для логарифма и экспоненты, а также тем, что <tex>m>0</tex>.

Таким образом, построенный нами <tex>\mathit{Verifier}</tex> корректен, а значит лемма доказана.
}}

{{Теорема
|statement=<tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
|proof=
Сведём язык <tex>\mathrm{TAUT}</tex> к языку <tex>\mathrm{\#SAT}</tex> следующим образом: <tex>\phi \mapsto \langle \phi, 2^k \rangle </tex>, где <tex>k</tex> — количество различных переменных в формуле <tex>\phi</tex>.

Очевидно, что <tex>\phi \in \mathrm{TAUT} \Leftrightarrow \langle \phi, 2^k \rangle \in \mathrm{\#SAT}</tex>.

По лемме (2) <tex>\mathrm{\#SAT} \in \mathrm{IP}</tex>. Тогда <tex>\mathrm{TAUT} \in \mathrm{IP}</tex>. Так как <tex>\mathrm{TAUT} \in \mathrm{coNPC}</tex>, то <tex>\mathrm{coNP} \subset \mathrm{IP}</tex>.
}}

[[Категория: Теория сложности]]

Теорема Махэни

2012-06-05T12:02:48Z

Байдаров Андрей:

Введём вспомогательный язык <tex>\mathrm{LSAT}</tex>.

{{Определение
|definition=
<tex>\mathrm{LSAT}=\{\langle\phi,y\rangle \bigm| \exists x: x\le_{lex}y, \phi(x) = 1\}</tex>.
}}

{{Лемма
|about=1
|statement=<tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>.
|proof=
#Очевидно, что <tex>\mathrm{LSAT} \in \mathrm{NP}</tex> (в качестве сертификата можно запросить <tex>x</tex>).
#Сведём <tex>\mathrm{SAT}</tex> к <tex>\mathrm{LSAT}</tex>. Для этого рассмотрим отображение <tex>\phi \mapsto \langle \phi, 1^{|\phi|}\rangle</tex>, где <tex>|\phi|</tex> — количество различных переменных в формуле <tex>\phi</tex>. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное.
#*Если <tex>\phi \in \mathrm{SAT}</tex>, то формула <tex>\phi</tex> удовлетворима, а значит <tex>\exists x: x \le_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Следовательно, <tex>\langle \phi, 1^{|\phi|}\rangle \in \mathrm{LSAT}</tex>.
#*Если <tex>\langle \phi, 1^{|\phi|}\rangle \in \mathrm{LSAT}</tex>, то <tex>\exists x: x \le_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Значит формула <tex>\phi</tex> удовлетворима, и <tex>\phi \in \mathrm{SAT}</tex>.
:Таким образом, <tex>\mathrm{SAT} \le \mathrm{LSAT}</tex>. Но <tex>\mathrm{SAT} \in \mathrm{NPC}</tex>, а значит <tex>\forall L \in \mathrm{NP} \; L \le \mathrm{SAT}</tex>. Тогда в силу транзитивности <tex>\forall L \in \mathrm{NP} \; L \le \mathrm{LSAT}</tex>, то есть <tex>\mathrm{LSAT} \in \mathrm{NPH}</tex>.
Итого мы доказали, что <tex>\mathrm{LSAT} \in \mathrm{NPH}</tex> и <tex>\mathrm{LSAT} \in \mathrm{NP}</tex>. Тогда по определению <tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>.
}}

{{Лемма
|about=2
|statement=<tex>\langle\phi,y\rangle \in \mathrm{LSAT}, y<_{lex}z</tex>. Тогда <tex>\langle\phi,z\rangle \in \mathrm{LSAT}</tex>.
|proof=<tex>\langle\phi,y\rangle \in \mathrm{LSAT}</tex>. Тогда <tex>\exists x: x\le_{lex}y, \phi(x) = 1</tex>. Так как <tex>y<_{lex}z</tex>, то <tex>\exists x: x<_{lex}z, \phi(x) = 1</tex>, следовательно <tex>\langle\phi,z\rangle \in \mathrm{LSAT}</tex>.
}}

{{Теорема
|author=Махэни
|statement=
<tex>\mathrm{NPC} \cap \mathrm{SPARSE} \ne \varnothing \Rightarrow \mathrm{P}=\mathrm{NP}</tex>.
|proof=Пусть <tex>S \in \mathrm{NPC} \cap \mathrm{SPARSE}</tex>.

Так как <tex>S\in \mathrm{NPC}</tex>, и <tex>\mathrm{LSAT} \in \mathrm{NP}</tex>, то существует полиномиальная функция сведения <tex>f</tex> такая, что <tex>\langle \phi, y \rangle \in \mathrm{LSAT} \Leftrightarrow f(\langle \phi, y \rangle) \in S</tex>.

Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\phi|=|y|</tex> (<tex>|y|</tex> — длина вектора <tex>y</tex>), то <tex>f(\langle\phi,y\rangle) \le q(|\phi|)</tex>, где <tex>q</tex> — полином.
<tex>S\in \mathrm{SPARSE}</tex>, следовательно <tex>\forall n \; |S \cap \Sigma^n|\le p(n)</tex>, где <tex>p</tex> — некоторый полином.

Тогда <tex>|\{x\in S \bigm| |x| \le q(|\phi|)\}| \le \sum\limits_{i=1}^{q(|\phi|)} p(i) = r(|\phi|)</tex>, где <tex>r</tex> — также полином.

Опишем алгоритм для нахождения лексикографически минимальной строки <tex>x</tex>, удовлетворяющей формуле <tex>\phi</tex>.

Пусть <tex>n=|\phi|, r=r(|\phi|)</tex>. Изначально область поиска для <tex>x</tex> — все строки длины <tex>n</tex>. Опишем одну итерацию поиска.

Разобьём текущее множество строк на <tex>r+1</tex> подотрезок примерно равной длины. Обозначим концы полученных подотрезков <tex>w_0,...,w_{r+1}</tex>. Пусть теперь <tex>z_i=f(\langle\phi,w_i\rangle)</tex>.

Из леммы (2) мы знаем, что, начиная с некоторого <tex>l</tex>, все пары <tex>\langle\phi, w_l\rangle \in \mathrm{LSAT}</tex>. Тогда по сведению <tex>z_j \in S</tex> для всех <tex>j\ge l</tex>.

Рассмотрим два случая:

# <tex>\exists i \ne j : z_i=z_j</tex>. Строки <tex>z_i</tex> и <tex>z_j</tex> либо обе лежат в <tex>S</tex>, либо обе не лежат в <tex>S</tex>. Тогда по вышеуказанной причине <tex>x\notin (w_i, w_j]</tex>. Значит мы можем исключить этот полуинтервал из рассматриваемого множества. Таким образом, мы удаляем не менее <tex>\frac 1{r+1}</tex> часть множества подстановок.
# <tex>z_i \ne z_j \, \forall i \ne j</tex>. Как было показано выше, если <tex>z_0</tex> или <tex>z_1</tex> лежит в <tex>S</tex>, то все последующие <tex>z_i</tex> тоже лежат в <tex>S</tex>, но тогда <tex>S</tex> содержит <tex>r+1</tex> строку длины не более, чем <tex>q(|\phi|)</tex>, что противоречит условию <tex>|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le r(|\phi|)</tex>. Следовательно, <tex>x\notin[w_0,w_1]</tex>, то есть его можно убрать из рассмотрения.

В обоих случаях мы сузили область поиска как минимум на <tex>\frac 1{r+1}</tex> её размера.

Будем повторять эту процедуру до тех пор, пока не останется не более <tex>r+1</tex> строки, которые мы можем проверить за полиномиальное время. Если какая-то из них удовлетворила формуле <tex>\phi</tex>, то <tex>x=min(w_i), w_i</tex> удовлетворяет <tex>\phi</tex>. Иначе, <tex>x</tex> не существует.

Оценим время работы нашего алгоритма. После <tex>k</tex> итераций у нас останется не более <tex>2^n(1-\frac1{r+1})^k</tex> строк. Оценим <tex>k</tex>.

<tex>2^n(1-\frac1{r+1})^k \simeq 1</tex>. Отсюда <tex>k=O(rn)</tex> (это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшись [http://ru.wikipedia.org/wiki/Ряд_Тейлора#.D0.A0.D1.8F.D0.B4.D1.8B_.D0.9C.D0.B0.D0.BA.D0.BB.D0.BE.D1.80.D0.B5.D0.BD.D0.B0_.D0.BD.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9 формулой Тейлора] для логарифма).

Таким образом, мы можем разрешить язык <tex>\mathrm{LSAT}</tex> за полиномиальное время, найдя лексикографически минимальную строку, удовлетворяющую формуле, и сравнив её с нашим аргументом. Так как <tex>\mathrm{LSAT}\in \mathrm{NPC}</tex>, то мы можем решить любую задачу из <tex>\mathrm{NP}</tex> за полиномиальное время, а значит <tex>\mathrm{P}=\mathrm{NP}</tex>.

}}

== См. также ==
*[[Класс P]]
*[[Классы NP и Σ₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Теорема Бермана — Форчуна]]

== Литература и источники информации ==
* [http://blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html Блог Computational Complexity]

[[Категория: Теория сложности]]

Интерактивные протоколы. Класс IP. Класс AM

2012-06-04T22:19:05Z

Байдаров Андрей: /* Язык GNI */

== Определения ==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>\mathit{Prover}</tex> и <tex>\mathit{Verifier}</tex>), такими, что
# <tex>\mathit{Prover}</tex> заинтересован в том, чтобы <tex>\mathit{Verifier}</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>\mathit{Prover}</tex> не ограничен в вычислительной мощности;
# <tex>\mathit{Verifier}</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;
# <tex>\mathit{Verifier}</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]];
# <tex>\mathit{Verifier}</tex> ограничен полиномиальным временем работы.
}}
[[Файл:IPS.png|250px|thumb|right|Схема интерактивного протокола.]]

<tex>\mathit{Verifier}</tex>, обменивающийся сообщениями с <tex>\mathit{Prover}</tex>, будем обозначать <tex>\mathit{Verifier^{Prover}}</tex>.

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>\mathit{Prover}</tex> к вероятностной ленте <tex>\mathit{Verifier}</tex>:
# public coins — <tex>\mathit{Prover}</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>;
# private coins — <tex>\mathit{Prover}</tex> не может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>.

{{Определение
|definition =
<tex>\mathrm{IP}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : </tex> 
# <tex>\mathit{Prover}</tex> не имеет доступа к вероятностной ленте <tex>\mathit{Verifier}</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>. 
}}
{{Определение
|definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex>
}}

Язык <tex>\mathrm{AM}</tex> (Arthur–Merlin games) отличается от <tex>\mathrm{IP}</tex> лишь тем, что <tex>\mathit{Prover}</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>.
{{Определение
|definition =
<tex>\mathrm{AM}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : </tex> 
# <tex>\mathit{Prover}</tex> может читать вероятностную ленту <tex>\mathit{Verifier}</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>. 
}}
{{Определение
|definition = <tex>\mathrm{AM}=\bigcup\limits_{p(n) \in poly} \mathrm{AM} [p(n)] </tex>
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness .
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness .
}}
Свойство completeness можно достичь, а soundness достичь нельзя.

== Соотношения с другими классами теории сложности ==

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP}[0]</tex>.
|proof=
<tex>\mathit{Verifier}</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>\mathit{Prover}</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP}[1]</tex>.
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>\mathit{Verifier}</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>\mathit{Prover}</tex>. Так как <tex>\mathit{Prover}</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>\mathit{Verifier}</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}

== Язык GNI ==
{{Определение
|definition=
<tex>\mathrm{GNI}</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>\mathrm{GNI}=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]</tex>.
|proof=
Будем использовать следующий алгоритм для <tex>\mathit{Verifier}</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>\mathit{Prover}</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP}[1]</tex>.
Во-первых, очевидно, что число раундов не превосходит двух. 
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>\mathit{Prover}</tex> сможет определить какой граф был перемешан <tex>\mathit{Verifier}</tex>. Таким образом, <tex>\mathit{Prover}</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>\mathit{Verifier}</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>\mathit{Prover}</tex> не сможет определить какой граф был перемешан <tex>\mathit{Verifier}</tex>. Так как <tex>\mathit{Prover}</tex> заинтересован в том, чтобы <tex>\mathit{Verifier}</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>\mathit{Verifier}</tex> просто вернёт <tex>0</tex>). Вероятность того, что <tex>\mathit{Verifier}</tex> примет слово <tex>x</tex>, когда оно не принадлежит языку (то есть <tex>\mathit{Prover}</tex> два раза подряд верно угадает номер графа), равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы NP и Σ₁]]

[[Категория: Теория сложности]]

Интерактивные протоколы. Класс IP. Класс AM

2012-06-04T22:13:38Z

Байдаров Андрей: /* Соотношения с другими классами теории сложности */

== Определения ==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>\mathit{Prover}</tex> и <tex>\mathit{Verifier}</tex>), такими, что
# <tex>\mathit{Prover}</tex> заинтересован в том, чтобы <tex>\mathit{Verifier}</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>\mathit{Prover}</tex> не ограничен в вычислительной мощности;
# <tex>\mathit{Verifier}</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;
# <tex>\mathit{Verifier}</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]];
# <tex>\mathit{Verifier}</tex> ограничен полиномиальным временем работы.
}}
[[Файл:IPS.png|250px|thumb|right|Схема интерактивного протокола.]]

<tex>\mathit{Verifier}</tex>, обменивающийся сообщениями с <tex>\mathit{Prover}</tex>, будем обозначать <tex>\mathit{Verifier^{Prover}}</tex>.

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>\mathit{Prover}</tex> к вероятностной ленте <tex>\mathit{Verifier}</tex>:
# public coins — <tex>\mathit{Prover}</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>;
# private coins — <tex>\mathit{Prover}</tex> не может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>.

{{Определение
|definition =
<tex>\mathrm{IP}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : </tex> 
# <tex>\mathit{Prover}</tex> не имеет доступа к вероятностной ленте <tex>\mathit{Verifier}</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>. 
}}
{{Определение
|definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex>
}}

Язык <tex>\mathrm{AM}</tex> (Arthur–Merlin games) отличается от <tex>\mathrm{IP}</tex> лишь тем, что <tex>\mathit{Prover}</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>.
{{Определение
|definition =
<tex>\mathrm{AM}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : </tex> 
# <tex>\mathit{Prover}</tex> может читать вероятностную ленту <tex>\mathit{Verifier}</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>. 
}}
{{Определение
|definition = <tex>\mathrm{AM}=\bigcup\limits_{p(n) \in poly} \mathrm{AM} [p(n)] </tex>
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness .
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness .
}}
Свойство completeness можно достичь, а soundness достичь нельзя.

== Соотношения с другими классами теории сложности ==

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP}[0]</tex>.
|proof=
<tex>\mathit{Verifier}</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>\mathit{Prover}</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP}[1]</tex>.
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>\mathit{Verifier}</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>\mathit{Prover}</tex>. Так как <tex>\mathit{Prover}</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>\mathit{Verifier}</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}

== Язык GNI ==
{{Определение
|definition=
<tex>\mathrm{GNI}</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>\mathrm{GNI}=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]</tex>.
|proof=
Будем использовать следующий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP}[1]</tex>.
Во-первых, очевидно, что число раундов не превосходит двух. 
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Вероятность того, что <tex>V</tex> примет слово <tex>x</tex>, когда оно не принадлежит языку (то есть <tex>P</tex> два раза подряд верно угадает номер графа), равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы NP и Σ₁]]

[[Категория: Теория сложности]]

Интерактивные протоколы. Класс IP. Класс AM

2012-06-04T22:08:35Z

Байдаров Андрей: /* Определения */

== Определения ==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>\mathit{Prover}</tex> и <tex>\mathit{Verifier}</tex>), такими, что
# <tex>\mathit{Prover}</tex> заинтересован в том, чтобы <tex>\mathit{Verifier}</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>\mathit{Prover}</tex> не ограничен в вычислительной мощности;
# <tex>\mathit{Verifier}</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;
# <tex>\mathit{Verifier}</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]];
# <tex>\mathit{Verifier}</tex> ограничен полиномиальным временем работы.
}}
[[Файл:IPS.png|250px|thumb|right|Схема интерактивного протокола.]]

<tex>\mathit{Verifier}</tex>, обменивающийся сообщениями с <tex>\mathit{Prover}</tex>, будем обозначать <tex>\mathit{Verifier^{Prover}}</tex>.

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>\mathit{Prover}</tex> к вероятностной ленте <tex>\mathit{Verifier}</tex>:
# public coins — <tex>\mathit{Prover}</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>;
# private coins — <tex>\mathit{Prover}</tex> не может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>.

{{Определение
|definition =
<tex>\mathrm{IP}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : </tex> 
# <tex>\mathit{Prover}</tex> не имеет доступа к вероятностной ленте <tex>\mathit{Verifier}</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>. 
}}
{{Определение
|definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex>
}}

Язык <tex>\mathrm{AM}</tex> (Arthur–Merlin games) отличается от <tex>\mathrm{IP}</tex> лишь тем, что <tex>\mathit{Prover}</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>.
{{Определение
|definition =
<tex>\mathrm{AM}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : </tex> 
# <tex>\mathit{Prover}</tex> может читать вероятностную ленту <tex>\mathit{Verifier}</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>. 
}}
{{Определение
|definition = <tex>\mathrm{AM}=\bigcup\limits_{p(n) \in poly} \mathrm{AM} [p(n)] </tex>
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness .
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness .
}}
Свойство completeness можно достичь, а soundness достичь нельзя.

== Соотношения с другими классами теории сложности ==

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP}[0]</tex>.
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP}[1]</tex>.
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}

== Язык GNI ==
{{Определение
|definition=
<tex>\mathrm{GNI}</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>\mathrm{GNI}=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]</tex>.
|proof=
Будем использовать следующий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP}[1]</tex>.
Во-первых, очевидно, что число раундов не превосходит двух. 
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Вероятность того, что <tex>V</tex> примет слово <tex>x</tex>, когда оно не принадлежит языку (то есть <tex>P</tex> два раза подряд верно угадает номер графа), равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы NP и Σ₁]]

[[Категория: Теория сложности]]

Интерактивные протоколы. Класс IP. Класс AM

2012-06-04T22:08:19Z

Байдаров Андрей: Отмена правки 23980 участника Байдаров Андрей (обсуждение)

== Определения ==

{{Определение
|definition =
Интерактивным протоколом, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (Prover и Verifier, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> заинтересован установить, действительно ли слово <tex>x</tex> принадлежит языку;
# <tex>V</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга|вероятностная машина Тьюринга]];
# <tex>V</tex> ограничен полиномиальным временем работы.
}}
[[Файл:IPS.png|250px|thumb|right|Схема интерактивного протокола.]]

<tex>V</tex>, обменивающийся сообщениями с <tex>P</tex>, будем обозначать <tex>V^{P}</tex>.

Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# public coins — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;
# private coins — <tex>P</tex> не может видеть вероятностную ленту <tex>V</tex>.

{{Определение
|definition =
<tex>\mathrm{IP}[f] = \{L\bigm|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V^{P}(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V^{P}(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>. 
}}
{{Определение
|definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex>
}}

Язык <tex>\mathrm{AM}</tex> (Arthur–Merlin games) отличается от <tex>\mathrm{IP}</tex> лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
|definition =
<tex>\mathrm{AM}[f] = \{L\bigm|\exists \langle V, P \rangle : </tex> 
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V^{P}(x) = 1) \ge \frac{2}{3} </tex>; 
# <tex> \forall x \notin L \Rightarrow P(V^{P}(x) = 1) \le \frac{1}{3} </tex>; 
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>. 
}}
{{Определение
|definition = <tex>\mathrm{AM}=\bigcup\limits_{p(n) \in poly} \mathrm{AM} [p(n)] </tex>
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V^{P}(x) = 1) = 1 </tex>, то говорят, что он обладает свойством completeness .
}}

{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V^{P}(x) = 1) = 0 </tex>, то говорят, что он обладает свойством soundness .
}}
Свойство completeness можно достичь, а soundness достичь нельзя.

== Соотношения с другими классами теории сложности ==

{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP}[0]</tex>.
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP}[1]</tex>.
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
<tex>V</tex> будет проверять на принадлежность слова <tex>x</tex> используя сертификат, который он запросит у <tex>P</tex>. Так как <tex>P</tex> не ограничен в вычислительной мощности, он может подобрать подходящий сертификат и именно его и сообщит, так как он заинтересован в том, чтобы <tex>V</tex> принял слово. Для этого требуется лишь один раунд интерактивного протокола.
}}

== Язык GNI ==
{{Определение
|definition=
<tex>\mathrm{GNI}</tex> расшифровывается как Graph Non Isomorphism. Это язык пар неизоморфных друг другу графов.
<tex>\mathrm{GNI}=\{ \langle G, H \rangle, </tex> графы <tex>G</tex> и <tex>H</tex> не изоморфны <tex>\}</tex>.
}}

{{Теорема
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]</tex>.
|proof=
Будем использовать следующий алгоритм для <tex>V</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; 
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; 
# Перешлём <tex>P</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; 
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; 
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; 
# Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу; 
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.

Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP}[1]</tex>.
Во-первых, очевидно, что число раундов не превосходит двух. 
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>P</tex> сможет определить какой граф был перемешан <tex>V</tex>. Таким образом, <tex>P</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>V</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>P</tex> не сможет определить какой граф был перемешан <tex>V</tex>. Так как <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>V</tex> просто вернёт <tex>0</tex>). Вероятность того, что <tex>V</tex> примет слово <tex>x</tex>, когда оно не принадлежит языку (то есть <tex>P</tex> два раза подряд верно угадает номер графа), равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы NP и Σ₁]]

[[Категория: Теория сложности]]

2012-06-02T16:56:00Z

Байдаров Андрей: /* Теорема */

===Hastad’s switching lemma===
{{Лемма
|statement=
Пусть <tex>f</tex> представима в виде <tex>k</tex>-[[ДНФ]], а <tex>p~-</tex> случайная выборка <tex>t</tex> случайных бит входа. Тогда при <tex>s \ge 2</tex> верно, что <tex>Pr[f|_p</tex> не представима в виде <tex>s</tex>-[[КНФ]]<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}.</tex>
|proof=
}}
Заметим, что для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.

===Теорема===
{{Определение
|definition=
<tex>\oplus~-</tex> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|язык]] над [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|алфавитом]] <tex>\left\{0, 1\right\}</tex>, состоящий из [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|слов]], содержащих нечетное число <tex>1.</tex>
}}

{{Теорема
|statement=
<tex>\oplus \notin \mathrm{AC^0}</tex>.
|proof=
Рассмотрим произвольную схему из <tex>\mathrm{AC^0}</tex>. Не умаляя общности, будем считать, что:
# Выходная степень каждого элемента равна <tex>1</tex>.
# Схема имеет <tex>2n</tex> входных провода, причем последние <tex>n</tex> из них являются отрицанием первых <tex>n</tex> входов.
# Элементы <tex>\lor</tex> и <tex>\land</tex> чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми.
# Нижний уровень схемы состоит из <tex>\land</tex> элементов с единичной степенью входа.

Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью уменьшить глубину схемы на <tex>1</tex>, сохранив при этом число входов. Пусть <tex>n~-</tex> длина входной цепочки, а <tex>d~-</tex> глубина схемы. Выберем минимальное целое <tex>b</tex> так, чтобы <tex>n^b</tex> было не меньше, чем число элементов в схеме. На каждом шаге случайным образом будем назначать все большее число переменных. Обозначим <tex>n_i~-</tex> число неназначенных переменных на <tex>i</tex>-ом шаге. Тогда на <tex>i + 1</tex>-ом шаге число назначенных переменных будет <tex>n_i - \sqrt{n_i}</tex>. Возьмем <tex>k_i=10b\cdot2^i.</tex>

[[Файл:beforeHastadSwitchingTransformation.png|600px|thumb|center|Схема на <tex>i</tex>-ом шаге.]]

Покажем, что после <tex>i+1</tex>-ого шага глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне будет <tex>k_i</tex>. В самом деле, пусть нижний уровень схемы состоит из <tex>\land</tex> элементов, тогда уровень выше <tex>-</tex> из элементов <tex>\lor</tex>. Каждый <tex>\lor</tex> элемент можно считать <tex>k_i</tex>-ДНФ. Отсюда по лемме получаем, что с вероятностью <tex>1-\left(\frac{k_i^{10}}{n^{1/2^{i+1}}}\right) ^ {k_{i+1}/2}</tex> функцию можно записать в виде <tex>k_{i+1}</tex>-КНФ. При достаточно больших <tex>n</tex> это можно сделать с вероятность хотя бы <tex>1-\frac{1}{10n^b}</tex>. Поскольку верхний уровень КНФ состоит из <tex>\land</tex> элементов, также как и уровень над КНФ, то их можно объединить, уменьшив при этом глубину схемы на <tex>1</tex>. Аналогично рассматриваем случай, когда нижний уровень схемы состоит из <tex>\lor</tex> элементов.

[[Файл:afterHastadSwitchingTransformation.png|600px|thumb|center|Схема на <tex>i+1</tex>-ом шаге.]]

Заметим, что лемма применяется не более, чем к <tex>n^b</tex> элементам исходной схемы. Тогда с вероятностью не менее <tex>9/10</tex> после <tex>d-2</tex>-ого шага получаем схему глубины <tex>2</tex>, у которой максимальная степень входа на нижнем уровне не больше <tex>k_{d-2}</tex>. По построению эта формула либо КНФ, либо ДНФ. Такую схему можно сделать постоянной, если правильно зафиксировать <tex>k_{d-2}</tex> переменных. Однако функцию, распознающую <tex>\oplus,</tex> невозможно сделать постоянной, зафиксировав менее <tex>n</tex> переменных. Получили противоречие. Поскольку рассматривали произвольную схему из класса <tex>\mathrm{AC^0}</tex>, верно что <tex>\oplus \notin \mathrm{AC^0}.</tex>
}}

===Источники===
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]

[[Категория: Теория сложности]]

Классы NC и AC

2012-06-02T15:01:37Z

Байдаров Андрей: /* Теоремы */

==Определения==
{{Определение
|definition=
<tex>\mathrm{NC^i}</tex> — множество языков, распознаваемых семейством логических схем полиномиального от <tex>n</tex> размера, глубиной <tex>O(log^i (n))</tex> и со степенью входа каждого элемента не более 2, причем существует детерминированная машина Тьюринга, принимающая на вход <tex>1^n</tex> и строящая соответствующую схему используя <tex>O(log(n))</tex> ячеек памяти, где <tex>n</tex> — длина входа.
}}

{{Определение
|definition=
<tex>\mathrm{AC^i}</tex> определяется аналогично <tex>\mathrm{NC^i}</tex>, за исключением того, что степень входа элемента неограничена.
}}

{{Определение
|definition=
<tex>\mathrm{NC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{NC^i}</tex>.
}}

{{Определение
|definition=
<tex>\mathrm{AC} = \bigcup \limits_{i = 0}^{\infty} \mathrm{AC^i}</tex>.
}}

==Теоремы==
{{Теорема
|statement=<tex>\mathrm{NC^i} \subset \mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex>.
|proof=
*<tex>\mathrm{NC^i} \subset \mathrm{AC^i}</tex> 
Это понятно из определения <tex>\mathrm{NC^i}</tex> и <tex>\mathrm{AC^i}</tex>. 
*<tex>\mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex> 
Пусть <tex>L \in \mathrm{AC^i}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex> полиномиального размера. Степень входа каждого элемента схемы <tex>C_n</tex> не превосходит полинома от <tex>n</tex>, поскольку степень входа не может превосходить число элементов в схеме. Заменим элементы схемы <tex>C_n</tex> элементами со степенью входа не более 2 следующим образом:

[[Файл:AndCircuit.png|500px|center]]

При такой замене глубина схемы увеличится не более чем в <tex>log_2 r(n) = O(log(n))</tex> раз, а так как изначально глубина схемы была <tex>O(log^i(n))</tex>, то после замены всех элементов она станет <tex>O(log^i(n)) \cdot O(log(n)) = O(log^{i+1}(n))</tex>. 
При замене одного элемента будет добавлено не более <tex>r(n)</tex> элементов, потому, поскольку изначальный размер схемы был полиномиальным и каждый элемент мы заменили полиномиальным числом элементов, после всех замен размер схемы останется полиномиальным.
}}
'''Следствие:''' <tex>\mathrm{NC} = \mathrm{AC}</tex>.

{{Теорема
|statement=<tex>\mathrm{NC} \subseteq \mathrm{P}</tex>.
|proof =
Пусть <tex>L \in \mathrm{NC}</tex>. Тогда <tex>L</tex> распознается некоторым семейством схем <tex>C_n</tex> таких, что существует детерминированная машина Тьюринга, строящая схему по <tex>1^n</tex>, используя <tex>O(log(n))</tex> ячеек памяти. Конфигурация МТ задается положением головки и состоянием ячеек памяти, то есть у МТ может быть <tex>n \cdot 2^{O(log(n))} = O(n^2)</tex> конфигураций. При построении схемы конфигурации не могут повторяться, иначе МТ зациклится, следовательно схема будет построена за полиномиальное от <tex>n</tex> время. Построим для данного входа схему и вычислим её. На вычисление схемы будет затрачено полиномиальное время, так как размер схемы полиномиален.}}
Равенство <tex>\mathrm{NC}</tex> и <tex>\mathrm{P}</tex> — неразрешенная на данный момент задача.

{{Утверждение
|about=тезис о связи <tex>\mathbf{NC}</tex> с параллельными алгоритмами
|statement=
<tex>L</tex> распознается параллельным компьютером с <tex>O(poly(n))</tex> процессоров за время <tex>O(poly(log(n))</tex> тогда и только тогда, когда <tex>L \in \mathrm{NC}</tex>.
|proof=
''(набросок доказательства)''

Пусть <tex>L \in \mathrm{NC}</tex>. <tex>L</tex> распознается семейством схем <tex>C_n</tex>, где <tex>C_n</tex> размера <tex>N=O(poly(n))</tex> и имеет глубину <tex>O(log^d n)</tex>. Возьмем параллельный компьютер с <tex>N</tex> процессорами, где каждый из них будет играть роль одного элемента схемы. Так как компьютер параллельный, то вычисления на каждом уровне схемы будут выполняться параллельно. Тогда получаем, что всего потребуется <tex>O(log^d(n))</tex> времени.

Пусть <tex>L</tex> распознается параллельным компьютером с <tex>N=O(poly(n))</tex> процессоров за время <tex>D=O(log^d n)</tex>. Построим схему глубины <tex>D</tex>, на каждом уровне которой будет по <tex>N</tex> элементов, таких, что <tex>i</tex>-й элемент на уровне <tex>t</tex> выполняет вычисления, производимые <tex>i</tex>-м процессором в момент времени <tex>t</tex>. Всего в схеме будет <tex>N \cdot D = O(poly(n)) \cdot O(log^d n) = O(poly(n))</tex> элементов.
}}

[[Категория: Теория сложности]]