315
правок
Изменения
Пока всё. Вечером, может быть, формулировки запилю.
= Доказательства =
== Теорема о двух эквивалентных определениях NP (NP = Sigma1) ==
{{Теорема
|statement=
<tex>\mathrm{\Sigma_1}=\mathrm{NP}</tex>.
|proof=
*<tex>\mathrm{\Sigma_1} \subset \mathrm{NP}</tex>.
Пусть <tex>L \in \mathrm{\Sigma_1}</tex>. Тогда существуют <tex>R(x,y)</tex> и полином <tex>p</tex> из определения <tex>\mathrm{\Sigma_1}</tex>. Построим недетерминированную программу <tex>q(x)</tex>, разрешающую <tex>L</tex>.
q(x):
y ← <tex>\{0,1\}^{p(|x|)}</tex>
return R(x,y)
Если <tex>x\in L</tex>, то программа сможет «угадать» подходящий сертификат. Если <tex>x\notin L</tex>, то подходящего сертификата не существует по определению. Таким образом, <tex>q</tex> разрешает <tex>L</tex>, следовательно <tex>L\in \mathrm{NP}</tex>.
*<tex>\mathrm{NP} \subset \mathrm{\Sigma_1}</tex>.
Пусть <tex>L\in \mathrm{NP}</tex>. Тогда существует недетерминированная программа <tex>q(x)</tex>, разрешающая этот язык. Построим верификатор <tex>R(x,y)</tex>. В качестве сертификата будем использовать последовательность выборов в программе <tex>q</tex>, приводящую к допуску слова (такой сертификат имеет полиномиальную длину, поскольку выборов в <tex>q</tex> может быть сделано не более, чем время ее работы, то есть не более, чем полином). Верификатор будет аналогичен программе <tex>q</tex>, только вместо каждого недетерминированного выбора он будет присваивать значение, указанное в сертификате. Если <tex>x\in L</tex>, то в <tex>q</tex> существует последовательность выборов таких, что <tex>q(x)=1</tex>, следовательно существует и верный сертификат. Если <tex>x\notin L</tex>, то для любой последовательности выборов <tex>q(x)=0</tex>, следовательно подходящего сертификата не существует. Таким образом, <tex>L \in \mathrm{\Sigma_1}</tex>.
}}
== Задача из NPC решается за полином => P = NP ==
Я этого не могу найти, но, казалось бы, это очевидно. Поэтому — отсебятина:
Любая задача из NP сводима по Карпу ({{TODO|t=тут, наверное, нужно написать про то, что за полином и почему}}) к любой задаче из NPC, поэтому, если задача из NPC решается за полином, то после сведения мы сможем решить за полином и любую задачу из NP
== Соотношение между P, NP, PS ==
Очевидно, что <tex>\mathrm{P} \subseteq \mathrm{NP}</tex>, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым.
{{Теорема
|statement =
<tex>\mathrm{P} \subseteq \mathrm{PS}</tex>.
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{P}</tex>. Так как <tex>L \in \mathrm{P}</tex>, то существует машина Тьюринга <tex>m</tex>, распознающая <tex>L</tex> за полиномиальное время. Это значит, что <tex>m</tex> не сможет использовать более, чем полиномиальное количество памяти, следовательно <tex> L \in \mathrm{PS}</tex>.
}}
{{Теорема
|statement =
<tex>\mathrm{NP} \subseteq \mathrm{PS}</tex>.
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{NP}</tex>. Так как <tex>L \in \mathrm{NP}</tex>, то существует программа-верификатор <tex>R(x,y)</tex>, что для каждого слова из <tex>L</tex> (и только для них) существует такой сертификат <tex>y</tex> полиномиальной длины, что <tex>R</tex> допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что <tex>L \in \mathrm{PS}</tex>.
}}
== Соотношение между L, NL, P ==
{{ Теорема
| statement = <tex>\mathrm{L} \subseteq \mathrm{NL}</tex>
| proof = Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <tex>\mathrm{L} \subseteq \mathrm{NL}</tex>.
}}
{{ Теорема
| statement = <tex>\mathrm{NL} \subseteq \mathrm{P}</tex> (следствие из предыдущей теоремы).
| proof = Необходимо доказать, что <tex>\forall \mathrm{B} \in \mathrm{NL}</tex> верно, что <tex>\mathrm{B} \in \mathrm{P}</tex>.
По определению <tex>\mathrm{A} \in \mathrm{NLC} \Leftrightarrow \mathrm{A} \in \mathrm{NL} </tex> и <tex>\forall \mathrm{B} \in \mathrm{NL} </tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}</tex>. Следовательно, если <tex>\exists \mathrm{A} \in \mathrm{NLC} : \mathrm{A} \in \mathrm{P}</tex>, то <tex>\forall \mathrm{B}</tex>, сводимого к <tex>\mathrm{A}</tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{P}} \mathrm{A}</tex>, следовательно, поскольку класс <tex>\mathrm{P}</tex> замкнут относительно <tex>\widetilde{\mathrm{P}}</tex>-сведения по Карпу, <tex>\mathrm{B} \in \mathrm{P}</tex>. Таким образом, если существует язык, принадлежащий <tex>\mathrm{NLC}</tex> и <tex>\mathrm{P}</tex>, то теорема доказана. Как было показано выше, <tex>\mathrm{CONN} \in \mathrm{NLC}</tex>. <tex>\mathrm{CONN} \in \mathrm{P}</tex>, что очевидно следует из существования алгоритма DFS.
}}
== Соотношение между ZPP, RP, BPP (вроде то, что нужно) ==
{{Теорема
|statement = <tex>\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
|proof =
Утверждение <tex>\mathrm{P} \subset \mathrm{ZPP}</tex> является очевидным, так как программы, удовлетворяющие ограничениям <tex>\mathrm{P}</tex>, также удовлетворяют ограничениям класса <tex>\mathrm{ZPP}</tex>.
Докажем, что <tex>\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
Для этого, покажем, что <tex>\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}</tex>. Тогда из <tex>\mathrm{ZPP} = \mathrm{ZPP}_1</tex> будет следовать требуемое.
1) <tex>\mathrm{ZPP}_1 \subset \mathrm{RP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>0</tex>.
2) <tex>\mathrm{ZPP}_1 \subset\mathrm{coRP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>1</tex>.
3) <tex>\mathrm{ZPP}_1 \supset \mathrm{RP} \cap \mathrm{coRP}</tex>.
Пусть программа <tex>p_1</tex> удовлетворяет ограничениям <tex>\mathrm{RP}</tex> и ошибается на словах из языка <tex>L</tex> с вероятностью не более <tex>1/2</tex>, а программа <tex>p_2</tex> удовлетворяет ограничениям <tex>\mathrm{coRP}</tex> и ошибается на словах не из языка <tex>L</tex> с аналогичной вероятностью. Построим программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex>:
<tex>q</tex>(x)
'''if''' <tex>p_2</tex>(x) = 0
'''return''' 0
'''if''' <tex>p_1</tex>(x) = 1
'''return''' 1
'''return''' ?
Вероятность вывести <tex>?</tex> есть <tex>\operatorname{P}(p_2(x) = 1, p_1(x) = 0) \le 1/2</tex>.
}}
{{Теорема
|statement =
<tex>\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}</tex>.
|proof =
Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
<tex>q</tex>(x)
u <- <tex>p</tex>(x)
v <- <tex>p</tex>(x)
'''return''' u '''or''' v
Пусть <tex>x \in L</tex>. В этом случае вероятность ошибки равна <tex>\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>.
Пусть <tex>x \notin L</tex>. Тогда с вероятностью <tex>1</tex> будет верно <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.
Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
}}
== BPP входит в PS ==
Либо я слепой, либо ещё что-то, не нашёл. Доказывается, наверное, несложно, но мне лень думать.
{{TODO|t=ЗАПИЛИТЬ}
== Интерактивное доказательство для GNI ==
{{Теорема
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]</tex>.
|proof=
Будем использовать следующий алгоритм для <tex>\mathit{Verifier}</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; <br/>
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; <br/>
# Перешлём <tex>\mathit{Prover}</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; <br/>
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; <br/>
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; <br/>
# Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу; <br/>
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.
Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP}[1]</tex>.
Во-первых, очевидно, что число раундов не превосходит двух. <br/>
Рассмотрим теперь случаи
* <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>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}
= Формулировки =
