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

Определения

Класс 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]: [math]|a_i| \leqslant f(i) [/math]; [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]: [math]P(p(x) = [x \in L]) \ge 2/3[/math]; [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]: [math]x \notin L \Rightarrow P(m(x) = 0) = 1[/math]; [math]x \in L \Rightarrow P(m(x) = 1) \geq \frac{1}{2}[/math]; [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]: [math]\operatorname{P}(p(x) \ne [x \in L]) = 0[/math]; [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]), такими, что [math]\mathit{Prover}[/math] заинтересован в том, чтобы [math]\mathit{Verifier}[/math] решил, что слово [math]x[/math] принадлежит языку; [math]\mathit{Prover}[/math] не ограничен в вычислительной мощности; [math]\mathit{Verifier}[/math] заинтересован установить, действительно ли слово [math]x[/math] принадлежит языку; [math]\mathit{Verifier}[/math] — вероятностная машина Тьюринга; [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] [math]\mathit{Prover}[/math] не имеет доступа к вероятностной ленте [math]\mathit{Verifier}[/math] (private coins); [math] \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} [/math]; [math] \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} [/math]; число раундов интерактивного протокола [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] [math]\mathit{Prover}[/math] может читать вероятностную ленту [math]\mathit{Verifier}[/math] (public coins); [math] \forall x \in L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \ge \frac{2}{3} [/math]; [math] \forall x \notin L \Rightarrow P(\mathit{Verifier^{Prover}}(x) = 1) \le \frac{1}{3} [/math]; число раундов интерактивного протокола [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]: Возьмём случайное число [math]i \in \{0, 1\}[/math] и случайную перестановку [math]\pi[/math] с вероятностной ленты; Создадим новый граф, перемешав вершины графа c номером [math]i[/math] перестановкой [math]\pi[/math]; Перешлём [math]\mathit{Prover}[/math] полученный граф с просьбой определить, из какого из исходных графов он был получен; Получив ответ, сравним его с правильным ответом — числом [math]i[/math]; Если полученный ответ не совпадёт с [math]i[/math], то вернём [math]0[/math]; Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу; Если мы ещё не вернули [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] их сертификаты, то есть: [math]x \in L \Leftrightarrow R(x, p(x)) = 1[/math]; для любой другой программы [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]