= Определения =
== Класс P ==
{{Определение
}}
== Видимо, это про NP-полные задачи полная задача ==
{{Определение
|definition =
<tex>\mathrm{NPC}</tex> является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс <tex>\mathrm{P}</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 ==
Оракул — абстракция, вычисляющая за <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{A}</tex> — множество языков, то <tex>\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}</tex>.
== Класс PS ==
<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-полная задача ==
Видимо{{Определение|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>:SkudarnovYaroslav#<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 ←? <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>}}
