Определения

Класс P

Определение:

Класс — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть: .

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

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

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

Определение:

.

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

Определение:

.

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

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

Определение:

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

Определение:

Язык [math]L_1[/math] [math]\widetilde{D}[/math]-сводится по Карпу к языку [math]L_2[/math] (), если существует такая функция из , что принадлежит тогда и только тогда, когда принадлежит :
.

Видимо, это про NP-полные задачи

Определение:

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

Определение:

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

Замечание. Часто используется сведение из [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].

Класс coNP

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

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

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

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

Определение:

Оракул — абстракция, вычисляющая за времени, верно ли, что принадлежит множеству .

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

Класс PS

Определение:

— класс языков, разрешимых на детерминированной машине Тьюринга с использованием памяти полиномиального размера.
.

Если [math]\mathrm{A}[/math] — множество языков, то .

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

Определение:

расшифровывается как True Quantified Boolean Formula. Это язык верных булевых формул с кванторами.
.

Утверждение:

Класс L

Определение:

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

Класс NL

Определение:

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

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

Определение:

Задача в графе G есть путь из s в t — задача существования пути между двумя заданными вершинами в данном графе.

Теорема:

Задача существования пути между двумя заданными вершинами в данном графе NL-полна относительно -сведения.

Класс P/poly

Определение:

— класс языков, разрешимых семейством логических схем полиномиального размера с n входами и одним выходом.

[math] \exists C_n [/math]:

[math] |C_n| \leqslant p(n)[/math], где [math] p [/math] — полином;
Число входов в схеме [math] C_n [/math] равно [math] n [/math];
Каждая схема [math] C_n [/math] имеет один выход;
.

Определение:

Пусть — сложностный класс, — функция. Тогда существуют подсказки и программа , удовлетворяющая ограничениям :

[math]|a_i| \leqslant f(i) [/math];
.

Определение:

.

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

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

Определение:

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

Определение:

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

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

Класс BPP

Определение:

(от bounded probabilistic polynomial) — множество языков , для которых существует такая ВМТ , что для любого :

;
[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]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

Определение:

(от zero-error probabilistic polynomial) — множество языков , для которых :

;
.

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

Напомним, что математическое ожидание является усреднением по вероятностным лентам, а не по входу [math]x[/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]:

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

Класс IP

Определение:

[math]\mathit{Prover}[/math] не имеет доступа к вероятностной ленте [math]\mathit{Verifier}[/math] (private coins);
;
;
число раундов интерактивного протокола [math] O(f(n)), n = |x|\}[/math].

Определение:

Класс AM

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

Определение:

[math]\mathit{Prover}[/math] может читать вероятностную ленту [math]\mathit{Verifier}[/math] (public coins);
;
;
число раундов интерактивного протокола [math] O(f(n)), n = |x|\} [/math].

Определение:

Класс PCP

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

Определение:

-системой (системой вероятностно проверяемых доказательств) с полнотой и обоснованностью над алфавитом для языка , где , называется верификатор — вероятностная машина Тьюринга, имеющая доступ к доказательству — цепочке из , удовлетворяющая следующим свойствам:

Полнота: если [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 (вероятностной сложностью) верификатора называется число случайных битов, используемых за всё время работы со входом длины .

Определение:

Query complexity (запросной сложностью) верификатора называется число запросов битов из , отсылаемых за всё время работы со входом длины .

Определение:

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

Определение:

Сложностный класс — это объединение всех языков, для которых существует -система над бинарным алфавитом с полнотой и обоснованностью , в которой неадаптивный верификатор работает за полиномиальное время и имеет вероятностную и запросную сложности соответственно и , а доказательства имеют экспоненциальную длину.
Часто обозначают как .

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

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

Теорема:

.

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

.

Пусть [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].

.

Пусть . Тогда существует недетерминированная программа , разрешающая этот язык. Построим верификатор . В качестве сертификата будем использовать последовательность выборов в программе , приводящую к допуску слова (такой сертификат имеет полиномиальную длину, поскольку выборов в может быть сделано не более, чем время ее работы, то есть не более, чем полином). Верификатор будет аналогичен программе , только вместо каждого недетерминированного выбора он будет присваивать значение, указанное в сертификате. Если , то в существует последовательность выборов таких, что , следовательно существует и верный сертификат. Если , то для любой последовательности выборов , следовательно подходящего сертификата не существует. Таким образом, .

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

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

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

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

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

Теорема:

.

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

Рассмотрим любой язык из . Так как , то существует машина Тьюринга , распознающая за полиномиальное время. Это значит, что не сможет использовать более, чем полиномиальное количество памяти, следовательно .

Теорема:

.

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

Рассмотрим любой язык из . Так как , то существует программа-верификатор , что для каждого слова из (и только для них) существует такой сертификат полиномиальной длины, что допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что .

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

Теорема:

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

Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому .

Теорема:

(следствие из предыдущей теоремы).

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

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

По определению и верно, что . Следовательно, если , то , сводимого к верно, что , следовательно, поскольку класс замкнут относительно -сведения по Карпу, . Таким образом, если существует язык, принадлежащий и , то теорема доказана. Как было показано выше, . , что очевидно следует из существования алгоритма DFS.

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

Теорема:

.

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

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

Докажем, что . Для этого, покажем, что . Тогда из будет следовать требуемое.

1) . Достаточно вместо [math]?[/math] возвращать [math]0[/math].

2) . Достаточно вместо [math]?[/math] возвращать [math]1[/math].

3) . Пусть программа [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]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]x \notin L[/math]. Тогда с вероятностью [math]1[/math] будет верно [math]u = 0, v = 0[/math] и [math]q[/math] вернет правильный ответ.

Аналогично доказывается, что .

BPP входит в PS

[math]BPP \subset PP[/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]\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]G[/math] и [math]H[/math] неизоморфны и [math]\mathit{Prover}[/math] сможет определить какой граф был перемешан [math]\mathit{Verifier}[/math]. Таким образом, [math]\mathit{Prover}[/math] сможет два раза подряд вернуть правильный ответ и в итоге [math]\mathit{Verifier}[/math] вернёт 1.
. Тогда [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].

Таким образом, построенный протокол удовлетворяет условию теоремы.

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

Определения

Класс P

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

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

Видимо, это про NP-полные задачи

Класс coNP

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

Класс PS

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

Класс L

Класс NL

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

Класс P/poly

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

Класс BPP

Класс RP

Класс ZPP

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

Класс IP

Класс AM

Класс PCP

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

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

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

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

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

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

BPP входит в PS

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

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

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты