Участник:SkudarnovYaroslav/Теормин к зачёту по теории сложности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(запилил что-то)
 
(Теорема о двух эквивалентных определениях NP (NP = Sigma1))
 
(не показано 17 промежуточных версий 5 участников)
Строка 1: Строка 1:
 +
= Определения =
 
== Класс P ==
 
== Класс P ==
 
{{Определение
 
{{Определение
Строка 35: Строка 36:
 
}}
 
}}
  
== Видимо, это про NP-полные задачи ==
+
== NP-полная задача ==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 51: Строка 52:
 
<tex>\mathrm{NPC}</tex> является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс <tex>\mathrm{P}</tex>,  
 
<tex>\mathrm{NPC}</tex> является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс <tex>\mathrm{P}</tex>,  
 
тогда окажется, что <tex>\mathrm{P} = \mathrm{NP}</tex>.
 
тогда окажется, что <tex>\mathrm{P} = \mathrm{NP}</tex>.
 +
 +
<tex> \mathrm{BH_{1N}} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex>, таких что недетерминированная машина Тьюринга <tex> m </tex> на входной строке <tex> x </tex> возращает <tex>1</tex> за время <tex> T(m, x) \le t </tex>.
 +
 +
<tex> \mathrm{BH_{1N}} = \lbrace \langle m, x, 1^t \rangle \bigm| m </tex> {{---}} недетерминированная машина Тьюринга, <tex> m(x) = 1, T(m,x) \le t \rbrace </tex>
 +
 +
{{Теорема
 +
|statement=<tex> \mathrm{BH_{1N}} \in \mathrm{NPC} </tex>
 +
}}
  
 
== Класс coNP ==
 
== Класс coNP ==
Строка 63: Строка 72:
 
Оракул — абстракция, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x</tex> принадлежит множеству <tex>A</tex>.
 
Оракул — абстракция, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x</tex> принадлежит множеству <tex>A</tex>.
 
}}
 
}}
Сложностный класс задач, решаемых алгоритмом из класса <tex>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.  
+
Сложностный класс задач, решаемых алгоритмом из класса <tex>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.
 +
Если <tex>\mathrm{A}</tex> — множество языков, то <tex>\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}</tex>.
  
 
== Класс PS ==
 
== Класс PS ==
Строка 70: Строка 80:
 
<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))</tex>.
 
<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))</tex>.
 
}}
 
}}
Если <tex>\mathrm{A}</tex> — множество языков, то <tex>\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}</tex>.
 
  
 
== PS-полная задача ==
 
== PS-полная задача ==
Видимо, [[Участник:SkudarnovYaroslav/Теормин к зачёту по теории сложности#Видимо, это про NP-полные задачи|тут]].
+
{{Определение
 +
|definition=<tex>\mathrm{TQBF}</tex> расшифровывается как '''True Quantified Boolean Formula'''. Это язык верных булевых формул с кванторами.<br/>
 +
<tex>\mathrm{TQBF}=\{Q_1 x_1 Q_2 x_2 \ldots Q_n x_n \phi(x_1, x_2, \dots, x_n), Q_i \in \{\forall, \exists\}\}</tex>.
 +
}}
 +
{{Утверждение
 +
|statement=<tex>\mathrm{TQBF} \in \mathrm{PSC}</tex>
 +
}}
 +
 
 +
== Класс L ==
 +
{{Определение
 +
|definition='''Класс <tex>\mathrm{L}</tex>''' — множество языков, разрешимых на детерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.
 +
<tex>\mathrm{L} = \mathrm{DSPACE}(\log n)</tex>.
 +
}}
 +
 
 +
== Класс NL ==
 +
{{Определение
 +
|definition='''Класс <tex>\mathrm{NL}</tex>''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.
 +
<tex>\mathrm{NL} = \mathrm{NSPACE}(\log n)</tex>.
 +
}}
 +
 
 +
== NL-полная задача ==
 +
{{ Определение
 +
|definition=Задача <tex>\mathrm{CONN} = \{\langle G, s, t \rangle \bigm|</tex> в графе G есть путь из s в t<tex>\}</tex> {{---}} задача существования пути между двумя заданными вершинами в данном графе.
 +
}}
 +
 
 +
{{ Теорема
 +
| statement = Задача существования пути между двумя заданными вершинами в данном графе NL-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|полна относительно <tex>\mathrm{\widetilde{L}}</tex>-сведения]].
 +
}}
 +
 
 +
== Класс P/poly ==
 +
{{Определение
 +
|definition=
 +
Пусть <tex> \mathrm{C} </tex> {{---}} сложностный класс, <tex> f </tex> {{---}} функция. Тогда <tex> \mathrm{C}/f = \{L \bigm| </tex> существуют подсказки <tex> a_0, a_1, \ldots , a_n, \ldots </tex> и программа <tex> p </tex>, удовлетворяющая ограничениям <tex> \mathrm{C} </tex>:
 +
#<tex>|a_i| \leqslant f(i) </tex>;
 +
#<tex> x \in L \Leftrightarrow p(x, a_{|x|})=1 \}</tex>.
 +
}}
 +
 
 +
{{Определение
 +
|definition=
 +
<tex> \mathrm{P/poly} = \bigcup\limits_{p \in poly} \mathrm{P}/p </tex>.
 +
}}
 +
 
 +
== Вероятностные вычисления (неформальненько как-то, ну да ладно) ==
 +
'''Вероятностные вычисления''' — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.
 +
 
 +
{{Определение
 +
|definition =
 +
'''Вероятностная лента''' — бесконечная в одну сторону последовательность битов, распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>).
 +
}}
 +
{{Определение
 +
|definition =
 +
'''Вероятностная машина Тьюринга''' (ВМТ) — детерминированная машина Тьюринга, имеющая вероятностную ленту. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной ленты.
 +
}}
 +
 
 +
Используя тезис Черча-Тьюринга, ВМТ можно сопоставить программы, имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом программы или ВМТ, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента.
 +
 
 +
== Класс BPP ==
 +
{{Определение
 +
|definition =
 +
<tex>\mathrm{BPP}</tex> (от ''bounded probabilistic polynomial'') — множество языков <tex>L</tex>, для которых существует такая [[Вероятностные вычисления. Вероятностная машина Тьюринга |ВМТ]] <tex>p</tex>, что для любого <tex>x</tex>:
 +
# <tex>P(p(x) = [x \in L]) \ge 2/3</tex>;
 +
# <tex>T(p, x) \le poly(|x|)</tex> для любой [[Вероятностные вычисления. Вероятностная машина Тьюринга |вероятностной ленты]].
 +
}}
 +
<tex>\mathrm{BPP}</tex> — сложностный класс, допускающий двусторонние ошибки.
 +
Константу <tex>2/3</tex> можно заменить на любое число из промежутка <tex>(1/2, 1)</tex>, так как требуемой вероятности можно добиться множественным запуском <tex>p</tex>. Замена константы на <tex>1/2</tex> сделала бы данный класс равным <tex>\Sigma^*</tex> (программа, возвращающая результат функции ''random''(), подошла бы для любого языка).
 +
 
 +
== Класс RP ==
 +
{{Определение
 +
|definition=
 +
Сложностный класс <tex>\mathrm{RP}</tex> состоит из языков <tex>L</tex> таких, что существует [[Вероятностные вычисления. Вероятностная машина Тьюринга|ВМТ]] <tex>m</tex> такая, что для любого <tex>x</tex>:
 +
# <tex>x \notin L \Rightarrow P(m(x) = 0) = 1</tex>;
 +
# <tex>x \in L \Rightarrow P(m(x) = 1) \geq \frac{1}{2}</tex>;
 +
# <tex>T(m(x, r)) \le poly(|x|)</tex> для любой вероятностной ленты <tex>r</tex>.
 +
}}
 +
<tex>\mathrm{RP}</tex> — сложностный класс, допускающий ошибки программ на словах из <tex>L</tex>.
 +
Заметим, что константа <tex>1/2</tex> в пункте 2 определения <tex>\mathrm{RP}</tex> может быть заменена на любую другую из промежутка <tex>(0, 1)</tex>, поскольку требуемой вероятности можно добиться множественным запуском программы.
 +
 
 +
<tex>\mathrm{RP}</tex> можно рассматривать как вероятностный аналог класса <tex>\mathrm{NP}</tex>, предполагая, что вероятность угадать сертификат в случае его существования не менее <tex>1/2</tex>.
 +
 
 +
== Класс ZPP ==
 +
{{Определение
 +
|definition =
 +
<tex>\mathrm{ZPP}</tex> (от ''zero-error probabilistic polynomial'') — множество языков <tex>L</tex>, для которых <tex>\exists p \forall x</tex>:
 +
# <tex>\operatorname{P}(p(x) \ne [x \in L]) = 0</tex>;<br>
 +
# <tex>\operatorname{E}[\operatorname{T}(p, x)] = poly(|x|)</tex>.<br>
 +
}}
 +
<tex>\mathrm{ZPP}</tex> — сложностный класс, такой что программы, удовлетворяющие его ограничениям, не могут делать ошибок, но работают за полиномиальное время только в среднем случае.
 +
 
 +
Напомним, что математическое ожидание является усреднением по вероятностным лентам, а не по входу <tex>x</tex>.
 +
 
 +
== Интерактивное доказательство (кажется, оно, но не уверен) ==
 +
{{Определение
 +
|definition =
 +
<b>Интерактивным протоколом</b>, разрешающим язык <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>:
 +
# <b> public coins </b> — <tex>\mathit{Prover}</tex> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>;
 +
# <b> private coins </b> — <tex>\mathit{Prover}</tex> <b>не</b> может видеть вероятностную ленту <tex>\mathit{Verifier}</tex>.
 +
 
 +
== Класс IP ==
 +
{{Определение
 +
|definition =
 +
<tex>\mathrm{IP}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : </tex> <br/>
 +
# <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>;<br/>
 +
# <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} </tex>;<br/>
 +
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.<br/>
 +
}}
 +
{{Определение
 +
|definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex>
 +
}}
 +
 
 +
== Класс AM ==
 +
Язык <tex>\mathrm{AM}</tex> (<i>Arthur–Merlin games</i>) отличается от <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> <br/>
 +
# <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>;<br/>
 +
# <tex> \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} </tex>;<br/>
 +
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>.<br/>
 +
}}
 +
{{Определение
 +
|definition = <tex>\mathrm{AM}=\bigcup\limits_{p(n) \in poly} \mathrm{AM} [p(n)] </tex>
 +
}}
 +
 
 +
== Класс PCP ==
 +
'''PCP(probabilistically checkable proof)''' - вид доказательства, проверяемого рандомизированным алгоритмом, использующим ограниченное число случайных бит и читающим ограниченное число бит доказательства. Такой алгоритм должен с достаточно высокими вероятностями принимать корректные доказательства и отвергать ошибочные.
 +
 
 +
{{Определение
 +
|definition =
 +
<tex>\mathrm{PCP}</tex>'''-системой''' (системой вероятностно проверяемых доказательств) с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex> над алфавитом <tex>\Sigma</tex> для языка <tex>L</tex>, где <tex>0 \le s(n) \le c(n) \le 1</tex>, называется верификатор <tex>V</tex> {{---}} [[Вероятностные вычисления. Вероятностная машина Тьюринга#Основные определения|вероятностная машина Тьюринга]], имеющая доступ к доказательству <tex>\pi</tex> {{---}} цепочке из <tex>\Sigma^{*}</tex>, удовлетворяющая следующим свойствам:
 +
* '''Полнота''': если <tex>x \in L</tex>, то вероятность того, что <tex>V^{\pi}</tex> допустит <tex>x</tex>, не меньше <tex>c(n)</tex> для некоторого <tex>\pi</tex>,
 +
* '''Обоснованность''': если <tex>x \notin L</tex>, то вероятность того, что <tex>V^{\pi}</tex> допустит <tex>x</tex>, не больше <tex>s(n)</tex> для любого <tex>\pi</tex>.
 +
}}
 +
{{Определение
 +
|definition =
 +
'''Randomness complexity''' (вероятностной сложностью) <tex>r(n)</tex> верификатора <tex>V</tex> называется число случайных битов, используемых за всё время работы со входом длины <tex>n</tex>.
 +
}}
 +
{{Определение
 +
|definition =
 +
'''Query complexity''' (запросной сложностью) <tex>q(n)</tex> верификатора <tex>V</tex> называется число запросов битов из <tex>\pi</tex>, отсылаемых за всё время работы со входом длины <tex>n</tex>.
 +
}}
 +
{{Определение
 +
|definition =
 +
Верификатор <tex>V</tex> называется '''non-adaptive''' (неадаптивным), если при отправке запроса не использует ответы на предыдущие. Иными словами, его работа не изменится, если все запросы отправить одновременно.
 +
}}
 +
{{Определение
 +
|definition =
 +
Сложностный класс <tex>\mathrm{PCP}_{c(n), s(n)}[r(n), q(n)]</tex> {{---}} это объединение всех языков, для которых существует <tex>\mathrm{PCP}</tex>-система над бинарным алфавитом с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex>, в которой неадаптивный верификатор <tex>V</tex> работает за полиномиальное время и имеет вероятностную и запросную сложности соответственно <tex>r(n)</tex> и <tex>q(n)</tex>, а доказательства имеют экспоненциальную длину.<br/>
 +
Часто <tex>\mathrm{PCP}_{1, \frac{1}{2}}[r(n), q(n)]</tex> обозначают как <tex>\mathrm{PCP}[r(n), q(n)]</tex>.
 +
}}
 +
 
 +
= Доказательства =
 +
== Теорема о двух эквивалентных определениях 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 &larr;? <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 сводима по Карпу к любой задаче из 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 ==
 +
<tex>BPP \subset PP</tex> (так как <tex>\forall p \forall x P(p(x) = [x \in L]) \geq \frac 2 3 \Rightarrow P(p(x) = [x \in L]) > \frac 1 2</tex>).
 +
 
 +
Пусть <tex>p</tex> — программа для языка <tex>L \in \mathrm{PP}</tex>. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для <tex>\mathrm{PS}</tex> будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них <tex>p</tex>. Ответом будет <tex>0</tex> или <tex>1</tex> в зависимости от того, каких ответов <tex>p</tex> оказалось больше.
 +
 
 +
== Интерактивное доказательство для 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>.
 +
Таким образом, построенный протокол удовлетворяет условию теоремы.
 +
}}
 +
 
 +
= Формулировки =
 +
== Теорема Кука ==
 +
<tex> \mathrm{SAT}</tex> {{---}} язык булевых формул из <tex> n </tex> переменных, для которых существует подстановка, при которой формула истинна.
 +
 
 +
<tex> \mathrm{SAT} = \lbrace \varphi \mid \exists x : \varphi(x) = 1 \rbrace </tex>
 +
 
 +
{{Теорема
 +
|author=Кук
 +
|statement=<tex> \mathrm{SAT}\in \mathrm{NPC} </tex>
 +
}}
 +
 
 +
== Теорема Ладнера ==
 +
{{Теорема
 +
|author=Ладнер
 +
|statement=
 +
<tex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \varnothing</tex>.
 +
}}
 +
 
 +
== Теорема Бейкера-Гилла-Соловея (не существует релятивизующегося доказательства P != NP) ==
 +
{{ Теорема
 +
|statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.
 +
}}
 +
 
 +
{{ Утверждение
 +
| statement = Если существует решение вопроса равенства <tex>\mathrm{P}</tex> и <tex> \mathrm{NP}</tex>, то оно не должно «релятивизоваться».
 +
}}
 +
 
 +
== Теорема Мэхени (нет редких NP-полных языков) ==
 +
{{Определение
 +
|definition=
 +
<tex>\mathrm{SPARSE} = \{L \bigm{|} \exists</tex> полином <tex>p: \forall n \, |L \cap \Sigma^n| \le p(n)\}</tex>.
 +
}}
 +
 
 +
{{Теорема
 +
|author=Махэни
 +
|statement=
 +
<tex>\mathrm{NPC} \cap \mathrm{SPARSE} \ne \varnothing \Rightarrow \mathrm{P}=\mathrm{NP}</tex>.
 +
}}
 +
 
 +
== Теорема Левина (об оптимальной NP-программе) ==
 +
{{Теорема
 +
|author=Левин
 +
|statement=
 +
Для любого языка <tex>L \in \Sigma_1</tex> и соответствующего ему (из определения <tex>\Sigma_1</tex>) отношения <tex>R</tex> существует «оптимальная» (работающая «не сильно дольше», чем любая другая) программа <tex>p</tex>, сопоставляющая словам из <tex>L</tex> их сертификаты, то есть:
 +
# <tex>x \in L \Leftrightarrow R(x, p(x)) = 1</tex>;
 +
# для любой другой программы <tex>q</tex>, для которой верно <tex>x \in L \Leftrightarrow R(x, q(x)) = 1</tex>, найдутся такие константа <tex>c</tex> и полином <tex>r</tex>, что для любого <tex>x</tex> выполняется: <tex>T(p, x) \le c \cdot T(q, x) + r(|x|)</tex>.
 +
}}
 +
 
 +
== Теорема Сэвича (PS = NPS) ==
 +
{{Теорема
 +
|statement =
 +
Для любой <tex>f(n) \ge \log n </tex> справедливо: <tex>\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)</tex>. <br>
 +
 
 +
То есть, если недетерминированная машина Тьюринга может решить проблему, используя <tex>f(n)</tex> памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем <tex>f(n)^2</tex> памяти.
 +
}}
 +
 
 +
== TQBF - PS-полная задача ==
 +
{{Определение
 +
|definition=<tex>\mathrm{TQBF}</tex> расшифровывается как '''True Quantified Boolean Formula'''. Это язык верных булевых формул с кванторами.<br/>
 +
<tex>\mathrm{TQBF}=\{Q_1 x_1 Q_2 x_2 \ldots Q_n x_n \phi(x_1, x_2, \dots, x_n), Q_i \in \{\forall, \exists\}\}</tex>.
 +
}}
 +
 
 +
{{Определение
 +
|definition=<tex>Quantified Boolean Formula</tex> — это пропозициональная формула с кванторами. Кванторы для каждой переменной записываются в начале выражения.
 +
}}
 +
 
 +
{{Теорема
 +
|statement=<tex>\mathrm{TQBF} \in \mathrm{PSC}</tex>.
 +
}}
 +
 
 +
== Теорема Иммермана (NL = coNL) ==
 +
{{ Теорема
 +
|statement = <tex>\mathrm{coNL} = \mathrm{NL}.</tex>
 +
}}
 +
 
 +
== Теоремы о полиномиальной иерархии ==
 +
{{Теорема
 +
|statement = Если существует <tex>i \colon \Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.
 +
}}
 +
 
 +
{{Теорема
 +
|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.
 +
}}
 +
 
 +
== Теорема Лаутемана (BPP и полиномиальная иерархия) ==
 +
{{ Теорема
 +
|about = Лаутеман
 +
|statement = <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>
 +
}}
 +
 
 +
== Теорема Шамира и др. (IP = PS) ==
 +
{{Теорема
 +
|author=Шамир
 +
|statement=<tex>\mathrm{IP} = \mathrm{PS}</tex>
 +
}}
 +
 
 +
== PCP-теорема ==
 +
{{Теорема
 +
|id=pcp_th
 +
|about=<tex>\mathrm{PCP}</tex> теорема
 +
|statement=<tex>\mathrm{PCP}[\log n, O(1)] = \mathrm{NP}</tex>
 +
}}

Текущая версия на 11:21, 6 июня 2013

Содержание

Определения

Класс P

Определение:
Класс [math]\mathrm{P}[/math] — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть: [math]\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))[/math].


Итого, язык [math]L[/math] лежит в классе [math]\mathrm{P}[/math] тогда и только тогда, когда существует такая детерминированная машина Тьюринга [math]m[/math], что:

  1. [math]m[/math] завершает свою работу за полиномиальное время на любых входных данных;
  2. если на вход машине [math]m[/math] подать слово [math]l \in L[/math], то она допустит его;
  3. если на вход машине [math]m[/math] подать слово [math]l \not\in L[/math], то она не допустит его.

Класс NP на языке недетерминированных машин и на языке сертификатов

Определение:
[math]\mathrm{NP}=\bigcup\limits_{p(n) \in poly}\mathrm{NTIME}(p(n))[/math].

То есть [math]\mathrm{NP}[/math] — это множество языков, разрешимых недетерминированной программой за полиномиальное время.


Определение:
[math]\mathrm{\Sigma_1}=\{L\bigm|\exists R(x,y)\in \tilde{\mathrm{P}}, p(n) - poly:x\in L\Leftrightarrow\exists y : |y|\le p(|x|), R(x,y)=1\}[/math].


Нестрого говоря, [math]\mathrm{\Sigma_1}[/math] — это множество языков, для которых существует работающая за полиномиальное время детерминированная программа-верификатор [math]R(x,y)[/math], а для каждого слова из языка (и только для слова из языка) можно предъявить сертификат полиномиальной длины, подтверждающий принадлежность слова языку и проверяемый верификатором.

Сведение по Карпу

Определение:
[math]D[/math] — класс языков, распознаваемых программами с некоторыми ограничениями. Тогда обозначим [math]\widetilde{D}[/math] класс вычислимых функций, вычисляемых программами с теми же ограничениями.


Определение:
Язык [math]L_1[/math] [math]\widetilde{D}[/math]-сводится по Карпу к языку [math]L_2[/math] ([math]L_1 \leq_{\widetilde{D}} L_2[/math]), если существует такая функция [math]f[/math] из [math]\widetilde{D}[/math], что [math]x[/math] принадлежит [math]L_1[/math] тогда и только тогда, когда [math]f(x)[/math] принадлежит [math]L_2[/math]:
[math] (L_1 \leq_{\widetilde{D}} L_2) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \widetilde{D} : x \in L_1 \Leftrightarrow f(x) \in L_2 ) [/math].


NP-полная задача

Определение:
[math]C[/math] — сложностный класс, [math]\widetilde{D}[/math] — класс вычислимых функций. Язык [math]L[/math] называется [math]C[/math]-трудным относительно [math]\widetilde{D}[/math]-сведения ([math]C[/math]-hard), если любой язык [math]M[/math] из [math]C[/math] [math]\widetilde{D}[/math]-сводится к [math]L[/math]:
[math] (L [/math][math]C[/math]-hard [math]) \overset{\underset{\mathrm{def}}{}}{\Leftrightarrow} ( \forall M \in C \Rightarrow M \leq_{f} L, f \in \widetilde{D} ) [/math].


Определение:
[math]C[/math] — сложностный класс, [math]\widetilde{D}[/math] — класс вычислимых функций. Язык [math]L[/math] называется [math]C[/math]-полным относительно [math]\widetilde{D}[/math]-сведения ([math]C[/math]-complete), если [math]L[/math] является [math]C[/math]-трудным относительно [math]\widetilde{D}[/math]-сведения и сам лежит в [math]C[/math].

Замечание. Часто используется сведение из [math]\widetilde{P}[/math], поэтому вместо «[math]\widetilde{P}[/math]-сводится по Карпу» говорят просто «сводится». Также индекс у символа сведения обычно опускают.

Класс [math]\mathrm{NP}[/math]-полных языков — [math]\mathrm{NPC}[/math]. [math]\mathrm{NPC}[/math] является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс [math]\mathrm{P}[/math], тогда окажется, что [math]\mathrm{P} = \mathrm{NP}[/math].

[math] \mathrm{BH_{1N}} [/math] — язык троек [math] \langle m, x, 1^t \rangle [/math], таких что недетерминированная машина Тьюринга [math] m [/math] на входной строке [math] x [/math] возращает [math]1[/math] за время [math] T(m, x) \le t [/math].

[math] \mathrm{BH_{1N}} = \lbrace \langle m, x, 1^t \rangle \bigm| m [/math] — недетерминированная машина Тьюринга, [math] m(x) = 1, T(m,x) \le t \rbrace [/math]

Теорема:
[math] \mathrm{BH_{1N}} \in \mathrm{NPC} [/math]

Класс coNP

В теории сложности класс co-NP — класс языков (задач), дополнение к которым лежит в NP.

co-NP = [math]\Pi_1[/math] (См. Полиномиальная иерархия)

Вычисление с оракулом

В теории вычислений и теории сложности "машиной с оракулом" называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости. Такая машина может быть представлена как машина Тьюринга, дополненная оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен решить определенные проблемы разрешимости за один такт машины Тьюринга. Машина Тьюринга взаимодействует с оракулом путем записи на свою ленту входных данных для оракула и затем его запуском на исполнение. За один шаг оракул вычисляет функцию, стирает входные данные и пишет выходные данные на ленту. Иногда машина Тьюринга описывается как имеющая две ленты, одна предназначена для входных данных оракула, другая — для выходных.

Определение:
Оракул — абстракция, вычисляющая за [math]O(1)[/math] времени, верно ли, что [math]x[/math] принадлежит множеству [math]A[/math].

Сложностный класс задач, решаемых алгоритмом из класса [math]\mathrm{C}[/math] с оракулом для языка [math]\mathrm{A}[/math], обозначают [math]\mathrm{C^A}[/math]. Если [math]\mathrm{A}[/math] — множество языков, то [math]\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}[/math].

Класс PS

Определение:
[math]\mathrm{PS}[/math] [math]\mathrm{(PSPACE)}[/math] — класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера.
[math]\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))[/math].


PS-полная задача

Определение:
[math]\mathrm{TQBF}[/math] расшифровывается как True Quantified Boolean Formula. Это язык верных булевых формул с кванторами.
[math]\mathrm{TQBF}=\{Q_1 x_1 Q_2 x_2 \ldots Q_n x_n \phi(x_1, x_2, \dots, x_n), Q_i \in \{\forall, \exists\}\}[/math].
Утверждение:
[math]\mathrm{TQBF} \in \mathrm{PSC}[/math]

Класс L

Определение:
Класс [math]\mathrm{L}[/math] — множество языков, разрешимых на детерминированной машине Тьюринга с использованием [math]O(\log n)[/math] дополнительной памяти для входа длиной [math]n[/math]. [math]\mathrm{L} = \mathrm{DSPACE}(\log n)[/math].


Класс NL

Определение:
Класс [math]\mathrm{NL}[/math] — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием [math]O(\log n)[/math] дополнительной памяти для входа длиной [math]n[/math]. [math]\mathrm{NL} = \mathrm{NSPACE}(\log n)[/math].


NL-полная задача

Определение:
Задача [math]\mathrm{CONN} = \{\langle G, s, t \rangle \bigm|[/math] в графе G есть путь из s в t[math]\}[/math] — задача существования пути между двумя заданными вершинами в данном графе.


Теорема:
Задача существования пути между двумя заданными вершинами в данном графе NL-полна относительно [math]\mathrm{\widetilde{L}}[/math]-сведения.

Класс P/poly

Определение:
Пусть [math] \mathrm{C} [/math] — сложностный класс, [math] f [/math] — функция. Тогда [math] \mathrm{C}/f = \{L \bigm| [/math] существуют подсказки [math] a_0, a_1, \ldots , a_n, \ldots [/math] и программа [math] p [/math], удовлетворяющая ограничениям [math] \mathrm{C} [/math]:
  1. [math]|a_i| \leqslant f(i) [/math];
  2. [math] x \in L \Leftrightarrow p(x, a_{|x|})=1 \}[/math].


Определение:
[math] \mathrm{P/poly} = \bigcup\limits_{p \in poly} \mathrm{P}/p [/math].


Вероятностные вычисления (неформальненько как-то, ну да ладно)

Вероятностные вычисления — один из подходов в теории вычислительной сложности, в котором программы получают доступ, говоря неформально, к генератору случайных чисел. Мы рассмотрим классы сложности, для которых программы могут работать за полиномиальное время и делать односторонние, двусторонние ошибки или работать за полиномиальное время лишь в среднем случае.


Определение:
Вероятностная лента — бесконечная в одну сторону последовательность битов, распределение которых подчиняется некоторому вероятностному закону (обычно считают, что биты в различных позициях независимы и вероятность нахождения [math]0[/math] или [math]1[/math] в каждой позиции равна [math]1/2[/math]).


Определение:
Вероятностная машина Тьюринга (ВМТ) — детерминированная машина Тьюринга, имеющая вероятностную ленту. Переходы в ВМТ могут осуществляться с учетом информации, считанной с вероятностной ленты.


Используя тезис Черча-Тьюринга, ВМТ можно сопоставить программы, имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции random(). При этом также будем предполагать, что вероятностная лента является неявным аргументом программы или ВМТ, т.е. [math]p(x) = p(x, r)[/math], где [math]r[/math] — вероятностная лента.

Класс BPP

Определение:
[math]\mathrm{BPP}[/math] (от bounded probabilistic polynomial) — множество языков [math]L[/math], для которых существует такая ВМТ [math]p[/math], что для любого [math]x[/math]:
  1. [math]P(p(x) = [x \in L]) \ge 2/3[/math];
  2. [math]T(p, x) \le poly(|x|)[/math] для любой вероятностной ленты.

[math]\mathrm{BPP}[/math] — сложностный класс, допускающий двусторонние ошибки. Константу [math]2/3[/math] можно заменить на любое число из промежутка [math](1/2, 1)[/math], так как требуемой вероятности можно добиться множественным запуском [math]p[/math]. Замена константы на [math]1/2[/math] сделала бы данный класс равным [math]\Sigma^*[/math] (программа, возвращающая результат функции random(), подошла бы для любого языка).

Класс RP

Определение:
Сложностный класс [math]\mathrm{RP}[/math] состоит из языков [math]L[/math] таких, что существует ВМТ [math]m[/math] такая, что для любого [math]x[/math]:
  1. [math]x \notin L \Rightarrow P(m(x) = 0) = 1[/math];
  2. [math]x \in L \Rightarrow P(m(x) = 1) \geq \frac{1}{2}[/math];
  3. [math]T(m(x, r)) \le poly(|x|)[/math] для любой вероятностной ленты [math]r[/math].

[math]\mathrm{RP}[/math] — сложностный класс, допускающий ошибки программ на словах из [math]L[/math]. Заметим, что константа [math]1/2[/math] в пункте 2 определения [math]\mathrm{RP}[/math] может быть заменена на любую другую из промежутка [math](0, 1)[/math], поскольку требуемой вероятности можно добиться множественным запуском программы.

[math]\mathrm{RP}[/math] можно рассматривать как вероятностный аналог класса [math]\mathrm{NP}[/math], предполагая, что вероятность угадать сертификат в случае его существования не менее [math]1/2[/math].

Класс ZPP

Определение:
[math]\mathrm{ZPP}[/math] (от zero-error probabilistic polynomial) — множество языков [math]L[/math], для которых [math]\exists p \forall x[/math]:
  1. [math]\operatorname{P}(p(x) \ne [x \in L]) = 0[/math];
  2. [math]\operatorname{E}[\operatorname{T}(p, x)] = poly(|x|)[/math].

[math]\mathrm{ZPP}[/math] — сложностный класс, такой что программы, удовлетворяющие его ограничениям, не могут делать ошибок, но работают за полиномиальное время только в среднем случае.

Напомним, что математическое ожидание является усреднением по вероятностным лентам, а не по входу [math]x[/math].

Интерактивное доказательство (кажется, оно, но не уверен)

Определение:
Интерактивным протоколом, разрешающим язык [math]L[/math], называется абстрактная машина (см. рисунок), моделирующая вычисления как обмен сообщениями между двумя программами ([math]\mathit{Prover}[/math] и [math]\mathit{Verifier}[/math]), такими, что
  1. [math]\mathit{Prover}[/math] заинтересован в том, чтобы [math]\mathit{Verifier}[/math] решил, что слово [math]x[/math] принадлежит языку;
  2. [math]\mathit{Prover}[/math] не ограничен в вычислительной мощности;
  3. [math]\mathit{Verifier}[/math] заинтересован установить, действительно ли слово [math]x[/math] принадлежит языку;
  4. [math]\mathit{Verifier}[/math]вероятностная машина Тьюринга;
  5. [math]\mathit{Verifier}[/math] ограничен полиномиальным временем работы.
Схема интерактивного протокола.

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

Интерактивные протоколы делятся на два типа в зависимости от доступа [math]\mathit{Prover}[/math] к вероятностной ленте [math]\mathit{Verifier}[/math]:

  1. public coins [math]\mathit{Prover}[/math] может видеть вероятностную ленту [math]\mathit{Verifier}[/math];
  2. private coins [math]\mathit{Prover}[/math] не может видеть вероятностную ленту [math]\mathit{Verifier}[/math].

Класс IP

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


Определение:
[math]\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] [/math]


Класс AM

Язык [math]\mathrm{AM}[/math] (Arthur–Merlin games) отличается от [math]\mathrm{IP}[/math] лишь тем, что [math]\mathit{Prover}[/math] может видеть вероятностную ленту [math]\mathit{Verifier}[/math].

Определение:
[math]\mathrm{AM}[f] = \{L\bigm|\exists \langle \mathit{Verifier}, \mathit{Prover} \rangle : [/math]
  1. [math]\mathit{Prover}[/math] может читать вероятностную ленту [math]\mathit{Verifier}[/math] (public coins);
  2. [math] \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} [/math];
  3. [math] \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} [/math];
  4. число раундов интерактивного протокола [math] O(f(n)), n = |x|\} [/math].


Определение:
[math]\mathrm{AM}=\bigcup\limits_{p(n) \in poly} \mathrm{AM} [p(n)] [/math]


Класс PCP

PCP(probabilistically checkable proof) - вид доказательства, проверяемого рандомизированным алгоритмом, использующим ограниченное число случайных бит и читающим ограниченное число бит доказательства. Такой алгоритм должен с достаточно высокими вероятностями принимать корректные доказательства и отвергать ошибочные.


Определение:
[math]\mathrm{PCP}[/math]-системой (системой вероятностно проверяемых доказательств) с полнотой [math]c(n)[/math] и обоснованностью [math]s(n)[/math] над алфавитом [math]\Sigma[/math] для языка [math]L[/math], где [math]0 \le s(n) \le c(n) \le 1[/math], называется верификатор [math]V[/math]вероятностная машина Тьюринга, имеющая доступ к доказательству [math]\pi[/math] — цепочке из [math]\Sigma^{*}[/math], удовлетворяющая следующим свойствам:
  • Полнота: если [math]x \in L[/math], то вероятность того, что [math]V^{\pi}[/math] допустит [math]x[/math], не меньше [math]c(n)[/math] для некоторого [math]\pi[/math],
  • Обоснованность: если [math]x \notin L[/math], то вероятность того, что [math]V^{\pi}[/math] допустит [math]x[/math], не больше [math]s(n)[/math] для любого [math]\pi[/math].


Определение:
Randomness complexity (вероятностной сложностью) [math]r(n)[/math] верификатора [math]V[/math] называется число случайных битов, используемых за всё время работы со входом длины [math]n[/math].


Определение:
Query complexity (запросной сложностью) [math]q(n)[/math] верификатора [math]V[/math] называется число запросов битов из [math]\pi[/math], отсылаемых за всё время работы со входом длины [math]n[/math].


Определение:
Верификатор [math]V[/math] называется non-adaptive (неадаптивным), если при отправке запроса не использует ответы на предыдущие. Иными словами, его работа не изменится, если все запросы отправить одновременно.


Определение:
Сложностный класс [math]\mathrm{PCP}_{c(n), s(n)}[r(n), q(n)][/math] — это объединение всех языков, для которых существует [math]\mathrm{PCP}[/math]-система над бинарным алфавитом с полнотой [math]c(n)[/math] и обоснованностью [math]s(n)[/math], в которой неадаптивный верификатор [math]V[/math] работает за полиномиальное время и имеет вероятностную и запросную сложности соответственно [math]r(n)[/math] и [math]q(n)[/math], а доказательства имеют экспоненциальную длину.
Часто [math]\mathrm{PCP}_{1, \frac{1}{2}}[r(n), q(n)][/math] обозначают как [math]\mathrm{PCP}[r(n), q(n)][/math].


Доказательства

Теорема о двух эквивалентных определениях NP (NP = Sigma1)

Теорема:
[math]\mathrm{\Sigma_1}=\mathrm{NP}[/math].
Доказательство:
[math]\triangleright[/math]
  • [math]\mathrm{\Sigma_1} \subset \mathrm{NP}[/math].

Пусть [math]L \in \mathrm{\Sigma_1}[/math]. Тогда существуют [math]R(x,y)[/math] и полином [math]p[/math] из определения [math]\mathrm{\Sigma_1}[/math]. Построим недетерминированную программу [math]q(x)[/math], разрешающую [math]L[/math].

 q(x):
   y ←? [math]\{0,1\}^{p(|x|)}[/math]
   return R(x,y)

Если [math]x\in L[/math], то программа сможет «угадать» подходящий сертификат. Если [math]x\notin L[/math], то подходящего сертификата не существует по определению. Таким образом, [math]q[/math] разрешает [math]L[/math], следовательно [math]L\in \mathrm{NP}[/math].

  • [math]\mathrm{NP} \subset \mathrm{\Sigma_1}[/math].
Пусть [math]L\in \mathrm{NP}[/math]. Тогда существует недетерминированная программа [math]q(x)[/math], разрешающая этот язык. Построим верификатор [math]R(x,y)[/math]. В качестве сертификата будем использовать последовательность выборов в программе [math]q[/math], приводящую к допуску слова (такой сертификат имеет полиномиальную длину, поскольку выборов в [math]q[/math] может быть сделано не более, чем время ее работы, то есть не более, чем полином). Верификатор будет аналогичен программе [math]q[/math], только вместо каждого недетерминированного выбора он будет присваивать значение, указанное в сертификате. Если [math]x\in L[/math], то в [math]q[/math] существует последовательность выборов таких, что [math]q(x)=1[/math], следовательно существует и верный сертификат. Если [math]x\notin L[/math], то для любой последовательности выборов [math]q(x)=0[/math], следовательно подходящего сертификата не существует. Таким образом, [math]L \in \mathrm{\Sigma_1}[/math].
[math]\triangleleft[/math]

Задача из NPC решается за полином => P = NP

Я этого не могу найти, но, казалось бы, это очевидно. Поэтому — отсебятина:

Любая задача из NP сводима по Карпу к любой задаче из NPC, поэтому, если задача из NPC решается за полином, то после сведения мы сможем решить за полином и любую задачу из NP.

Соотношение между P, NP, PS

Очевидно, что [math]\mathrm{P} \subseteq \mathrm{NP}[/math], так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым.

Теорема:
[math]\mathrm{P} \subseteq \mathrm{PS}[/math].
Доказательство:
[math]\triangleright[/math]
Рассмотрим любой язык [math]L[/math] из [math]\mathrm{P}[/math]. Так как [math]L \in \mathrm{P}[/math], то существует машина Тьюринга [math]m[/math], распознающая [math]L[/math] за полиномиальное время. Это значит, что [math]m[/math] не сможет использовать более, чем полиномиальное количество памяти, следовательно [math] L \in \mathrm{PS}[/math].
[math]\triangleleft[/math]
Теорема:
[math]\mathrm{NP} \subseteq \mathrm{PS}[/math].
Доказательство:
[math]\triangleright[/math]
Рассмотрим любой язык [math]L[/math] из [math]\mathrm{NP}[/math]. Так как [math]L \in \mathrm{NP}[/math], то существует программа-верификатор [math]R(x,y)[/math], что для каждого слова из [math]L[/math] (и только для них) существует такой сертификат [math]y[/math] полиномиальной длины, что [math]R[/math] допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что [math]L \in \mathrm{PS}[/math].
[math]\triangleleft[/math]

Соотношение между L, NL, P

Теорема:
[math]\mathrm{L} \subseteq \mathrm{NL}[/math]
Доказательство:
[math]\triangleright[/math]
Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому [math]\mathrm{L} \subseteq \mathrm{NL}[/math].
[math]\triangleleft[/math]
Теорема:
[math]\mathrm{NL} \subseteq \mathrm{P}[/math] (следствие из предыдущей теоремы).
Доказательство:
[math]\triangleright[/math]

Необходимо доказать, что [math]\forall \mathrm{B} \in \mathrm{NL}[/math] верно, что [math]\mathrm{B} \in \mathrm{P}[/math].

По определению [math]\mathrm{A} \in \mathrm{NLC} \Leftrightarrow \mathrm{A} \in \mathrm{NL} [/math] и [math]\forall \mathrm{B} \in \mathrm{NL} [/math] верно, что [math]\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}[/math]. Следовательно, если [math]\exists \mathrm{A} \in \mathrm{NLC} : \mathrm{A} \in \mathrm{P}[/math], то [math]\forall \mathrm{B}[/math], сводимого к [math]\mathrm{A}[/math] верно, что [math]\mathrm{B} \leq_{\widetilde{P}} \mathrm{A}[/math], следовательно, поскольку класс [math]\mathrm{P}[/math] замкнут относительно [math]\widetilde{\mathrm{P}}[/math]-сведения по Карпу, [math]\mathrm{B} \in \mathrm{P}[/math]. Таким образом, если существует язык, принадлежащий [math]\mathrm{NLC}[/math] и [math]\mathrm{P}[/math], то теорема доказана. Как было показано выше, [math]\mathrm{CONN} \in \mathrm{NLC}[/math]. [math]\mathrm{CONN} \in \mathrm{P}[/math], что очевидно следует из существования алгоритма DFS.
[math]\triangleleft[/math]

Соотношение между ZPP, RP, BPP (вроде то, что нужно)

Теорема:
[math]\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}[/math].
Доказательство:
[math]\triangleright[/math]

Утверждение [math]\mathrm{P} \subset \mathrm{ZPP}[/math] является очевидным, так как программы, удовлетворяющие ограничениям [math]\mathrm{P}[/math], также удовлетворяют ограничениям класса [math]\mathrm{ZPP}[/math].

Докажем, что [math]\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}[/math]. Для этого, покажем, что [math]\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}[/math]. Тогда из [math]\mathrm{ZPP} = \mathrm{ZPP}_1[/math] будет следовать требуемое.

1) [math]\mathrm{ZPP}_1 \subset \mathrm{RP}[/math]. Достаточно вместо [math]?[/math] возвращать [math]0[/math].

2) [math]\mathrm{ZPP}_1 \subset\mathrm{coRP}[/math]. Достаточно вместо [math]?[/math] возвращать [math]1[/math].

3) [math]\mathrm{ZPP}_1 \supset \mathrm{RP} \cap \mathrm{coRP}[/math]. Пусть программа [math]p_1[/math] удовлетворяет ограничениям [math]\mathrm{RP}[/math] и ошибается на словах из языка [math]L[/math] с вероятностью не более [math]1/2[/math], а программа [math]p_2[/math] удовлетворяет ограничениям [math]\mathrm{coRP}[/math] и ошибается на словах не из языка [math]L[/math] с аналогичной вероятностью. Построим программу [math]q[/math] для [math]\mathrm{ZPP}_1[/math]:

 [math]q[/math](x)
   if [math]p_2[/math](x) = 0
     return 0
   if [math]p_1[/math](x) = 1
     return 1
   return ?
Вероятность вывести [math]?[/math] есть [math]\operatorname{P}(p_2(x) = 1, p_1(x) = 0) \le 1/2[/math].
[math]\triangleleft[/math]
Теорема:
[math]\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]p[/math] — программа для [math]L \in \mathrm{RP}[/math]. Программу [math]q[/math] для [math]\mathrm{BPP}[/math] определим следующим образом:

 [math]q[/math](x)
   u <- [math]p[/math](x)
   v <- [math]p[/math](x)
   return u or v

Пусть [math]x \in L[/math]. В этом случае вероятность ошибки равна [math]\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4[/math].

Пусть [math]x \notin L[/math]. Тогда с вероятностью [math]1[/math] будет верно [math]u = 0, v = 0[/math] и [math]q[/math] вернет правильный ответ.

Аналогично доказывается, что [math]\mathrm{coRP} \subset \mathrm{BPP}[/math].
[math]\triangleleft[/math]

BPP входит в PS

[math]BPP \subset PP[/math] (так как [math]\forall p \forall x P(p(x) = [x \in L]) \geq \frac 2 3 \Rightarrow P(p(x) = [x \in L]) \gt \frac 1 2[/math]).

Пусть [math]p[/math] — программа для языка [math]L \in \mathrm{PP}[/math]. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для [math]\mathrm{PS}[/math] будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них [math]p[/math]. Ответом будет [math]0[/math] или [math]1[/math] в зависимости от того, каких ответов [math]p[/math] оказалось больше.

Интерактивное доказательство для GNI

Теорема:
[math]\mathrm{GNI} \in \mathrm{IP}[1][/math].
Доказательство:
[math]\triangleright[/math]

Будем использовать следующий алгоритм для [math]\mathit{Verifier}[/math]:

  1. Возьмём случайное число [math]i \in \{0, 1\}[/math] и случайную перестановку [math]\pi[/math] с вероятностной ленты;
  2. Создадим новый граф, перемешав вершины графа c номером [math]i[/math] перестановкой [math]\pi[/math];
  3. Перешлём [math]\mathit{Prover}[/math] полученный граф с просьбой определить, из какого из исходных графов он был получен;
  4. Получив ответ, сравним его с правильным ответом — числом [math]i[/math];
  5. Если полученный ответ не совпадёт с [math]i[/math], то вернём [math]0[/math];
  6. Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу;
  7. Если мы ещё не вернули [math]0[/math], то вернём [math]1[/math].

Покажем, что это удовлетворяет ограничениям на [math]\mathrm{IP}[1][/math]. Во-первых, очевидно, что число раундов не превосходит двух.
Рассмотрим теперь случаи

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

Формулировки

Теорема Кука

[math] \mathrm{SAT}[/math] — язык булевых формул из [math] n [/math] переменных, для которых существует подстановка, при которой формула истинна.

[math] \mathrm{SAT} = \lbrace \varphi \mid \exists x : \varphi(x) = 1 \rbrace [/math]

Теорема (Кук):
[math] \mathrm{SAT}\in \mathrm{NPC} [/math]

Теорема Ладнера

Теорема (Ладнер):
[math]\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \varnothing[/math].

Теорема Бейкера-Гилла-Соловея (не существует релятивизующегося доказательства P != NP)

Теорема:
Существуют такие оракулы [math]A[/math] и [math]B[/math], что [math]\mathrm{P^A} = \mathrm{NP^A} [/math] и [math]\mathrm{P^B} \ne \mathrm{NP^B} [/math].
Утверждение:
Если существует решение вопроса равенства [math]\mathrm{P}[/math] и [math] \mathrm{NP}[/math], то оно не должно «релятивизоваться».

Теорема Мэхени (нет редких NP-полных языков)

Определение:
[math]\mathrm{SPARSE} = \{L \bigm{|} \exists[/math] полином [math]p: \forall n \, |L \cap \Sigma^n| \le p(n)\}[/math].


Теорема (Махэни):
[math]\mathrm{NPC} \cap \mathrm{SPARSE} \ne \varnothing \Rightarrow \mathrm{P}=\mathrm{NP}[/math].

Теорема Левина (об оптимальной NP-программе)

Теорема (Левин):
Для любого языка [math]L \in \Sigma_1[/math] и соответствующего ему (из определения [math]\Sigma_1[/math]) отношения [math]R[/math] существует «оптимальная» (работающая «не сильно дольше», чем любая другая) программа [math]p[/math], сопоставляющая словам из [math]L[/math] их сертификаты, то есть:
  1. [math]x \in L \Leftrightarrow R(x, p(x)) = 1[/math];
  2. для любой другой программы [math]q[/math], для которой верно [math]x \in L \Leftrightarrow R(x, q(x)) = 1[/math], найдутся такие константа [math]c[/math] и полином [math]r[/math], что для любого [math]x[/math] выполняется: [math]T(p, x) \le c \cdot T(q, x) + r(|x|)[/math].

Теорема Сэвича (PS = NPS)

Теорема:
Для любой [math]f(n) \ge \log n [/math] справедливо: [math]\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)[/math].
То есть, если недетерминированная машина Тьюринга может решить проблему, используя [math]f(n)[/math] памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем [math]f(n)^2[/math] памяти.

TQBF - PS-полная задача

Определение:
[math]\mathrm{TQBF}[/math] расшифровывается как True Quantified Boolean Formula. Это язык верных булевых формул с кванторами.
[math]\mathrm{TQBF}=\{Q_1 x_1 Q_2 x_2 \ldots Q_n x_n \phi(x_1, x_2, \dots, x_n), Q_i \in \{\forall, \exists\}\}[/math].


Определение:
[math]Quantified Boolean Formula[/math] — это пропозициональная формула с кванторами. Кванторы для каждой переменной записываются в начале выражения.


Теорема:
[math]\mathrm{TQBF} \in \mathrm{PSC}[/math].

Теорема Иммермана (NL = coNL)

Теорема:
[math]\mathrm{coNL} = \mathrm{NL}.[/math]

Теоремы о полиномиальной иерархии

Теорема:
Если существует [math]i \colon \Sigma_i = \Sigma_{i+1}[/math], то [math]\Sigma_i = \mathrm{PH}[/math].
Теорема:
Если существует [math]i \gt 0\colon \Sigma_i = \Pi_i[/math], то [math]\Sigma_i = \mathrm{PH}[/math].

Теорема Лаутемана (BPP и полиномиальная иерархия)

Теорема (Лаутеман):
[math]\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}[/math]

Теорема Шамира и др. (IP = PS)

Теорема (Шамир):
[math]\mathrm{IP} = \mathrm{PS}[/math]

PCP-теорема

Теорема ([math]\mathrm{PCP}[/math] теорема):
[math]\mathrm{PCP}[\log n, O(1)] = \mathrm{NP}[/math]