315
правок
Изменения
Определения всё
== PS-полная задача ==
Видимо, [[Участник:SkudarnovYaroslav/Теормин к зачёту по теории сложности#Видимо, это про NP-полные задачи|тут]].
== Класс 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-полная задача ==
Опять же, [[Участник:SkudarnovYaroslav/Теормин к зачёту по теории сложности#Видимо, это про NP-полные задачи|тут]].
== Класс P/poly ==
{{Определение
|definition=
<tex> \mathrm{PSIZE} </tex> {{---}} класс языков, разрешимых семейством [[Реализация_булевой_функции_схемой_из_функциональных_элементов|логических схем]] <tex> \{C_n\}_{n>0} </tex> полиномиального размера с n входами и одним выходом.
<tex> \mathrm{PSIZE} =\{L \bigm| \forall n </tex> <tex> \exists C_n </tex>:
#<tex> |C_n| \leqslant p(n)</tex>, где <tex> p </tex> {{---}} полином;
#Число входов в схеме <tex> C_n </tex> равно <tex> n </tex>;
#Каждая схема <tex> C_n </tex> имеет один выход;
#<tex>x \in L \Leftrightarrow C_{|x|}(x) = 1 \}</tex>.
}}
{{Определение
|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>.
}}
