Викиконспекты - Вклад участника [ru]

Теорема о включении BPP в P/poly

2010-06-17T00:48:51Z

Vadim: /* Формулировка */

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

<tex>BPP \subset P/poly</tex>

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

Для доказательства данной теоремы воспользуемся сильным определением [[Сложностный_класс_BPP|BPP]]. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <tex> x </tex> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <tex> BPP </tex> и добьёмся вероятности ошибки <tex> \frac{1}{2^{n+1}}</tex>, где <tex> n = |x| </tex> (длина входа). Будем говорить, что <tex> r </tex> "плохо" для <tex> x </tex>, если ответ неверный. Пусть <tex> t </tex> общее количество выборов для <tex> r </tex>. Для каждого <tex> x </tex> по крайне мере <tex> \frac{t}{2^{n+1}}</tex> "плохих" значений <tex> r</tex>. Cуммирую по всем <tex> x </tex>, мы получим, что по крайне мере <tex> \frac{t*2^{n}}{2^{n+1}}</tex> "плохих" <tex> r </tex> для <tex> x </tex>. С другой стороны, хотя бы <tex> t/2 </tex> значений <tex> r </tex> не "плохи" для любого <tex> x </tex>. Получается, что точно найдётся такое <tex> r </tex>, при котором будет получается всегда верный результат. Таким образом мы получили, что язык из <tex> BPP </tex> принадлежит <tex>P/poly</tex>.

Теорема о включении BPP в P/poly

2010-06-17T00:48:30Z

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

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

<math>BPP \subset P/poly</math>

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

Для доказательства данной теоремы воспользуемся сильным определением [[Сложностный_класс_BPP|BPP]]. Возьмём случайную последовательность, как дополнительный вход, который будет решать для любого входа <tex> x </tex> c экспоненцальной низкой вероятностью ошибки. Зафиксируем язык из <tex> BPP </tex> и добьёмся вероятности ошибки <tex> \frac{1}{2^{n+1}}</tex>, где <tex> n = |x| </tex> (длина входа). Будем говорить, что <tex> r </tex> "плохо" для <tex> x </tex>, если ответ неверный. Пусть <tex> t </tex> общее количество выборов для <tex> r </tex>. Для каждого <tex> x </tex> по крайне мере <tex> \frac{t}{2^{n+1}}</tex> "плохих" значений <tex> r</tex>. Cуммирую по всем <tex> x </tex>, мы получим, что по крайне мере <tex> \frac{t*2^{n}}{2^{n+1}}</tex> "плохих" <tex> r </tex> для <tex> x </tex>. С другой стороны, хотя бы <tex> t/2 </tex> значений <tex> r </tex> не "плохи" для любого <tex> x </tex>. Получается, что точно найдётся такое <tex> r </tex>, при котором будет получается всегда верный результат. Таким образом мы получили, что язык из <tex> BPP </tex> принадлежит <tex>P/poly</tex>.

Классы EXP, NEXP. Полнота языков EXP и NEXP

2010-06-17T00:39:35Z

Vadim: /* Полнота класса NEXP */

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

<tex>EXP = \bigcup^{\infty}_{i=0}DTIME(2^{n^{i}})</tex>

<tex>NEXP = \bigcup^{\infty}_{i=0}NTIME(2^{n^{i}})</tex>

== Полная задача в классе ''EXP'' ==

=== Существует полная в ''EXP'' задача ===
====Доказательство====

Полной задачей в <tex>EXP</tex> является задача <tex>BH_{2,D}</tex>(binary deterministic bounded halt):
<tex>BH_{2,D} =\{ \langle m, x, t\rangle \mid m(x) = 1, T(m,x) \le t \}</tex>

(<tex>t</tex> задаётся двоичной записью, <tex>m</tex> - детерминированная машина Тьюринга)

Докажем, что <tex>BH_{2,D} \in EXP</tex>. Симулируем работу детерминированной машины <tex>m</tex>. Для этого потребуется время порядка <tex>t^{2}</tex>, но <tex>t \le 2^{|t|} \le 2^{|\langle m,x,t \rangle|}</tex>. Таким образом, общее время работы <tex>T \le (2^{|\langle m,x,t \rangle|})^{2} = 2^{2n}</tex> и <tex>BH_{2,D} \in EXP</tex>.
Докажем, что любая задача из <tex>EXP</tex> сводится к <tex>BH_{2,D}</tex>. Пусть <tex>L \in EXP, MT\enskip m</tex>, допускающая язык <tex>L</tex>, работает за время <tex>T \le 2^{p(n)}</tex>, где <tex>p(n)</tex> - полином. Рассмотрим <tex>f : x \rightarrow \langle m,x,2^{p(n)} \rangle</tex> - функция сведения. Чтобы выписать свой результат на ленту ей потребуется полиномиальное от <tex>n</tex> число шагов, так как запись <tex>m</tex> имеет константную длину, <tex>|x| = n</tex> и запись числа <tex>2^{p(n)}</tex> имеет длину порядка <tex>p(n)</tex> в двоичной системе.

== Полная задача в классе ''NEXP'' ==

=== Существует полная в ''NEXP'' задача ===
====Доказательство====

Полной задачей в <tex>NEXP</tex> является задача <tex>BH_{2,N}</tex>(binary nondeterministic bounded halt):
<tex>BH_{2,N} =\{ \langle m, x, t \rangle \mid m(x) = 1, T(m,x) \le t \}</tex>

(<tex>t</tex> задаётся двоичной записью, <tex>m</tex> - недетерминированная машина Тьюринга)

Доказательство того, что <tex>BH_{2,N}</tex> - полная задача в <tex>NEXP</tex>, аналогично предыдушему доказательству. Заметим, что при симуляции работы <tex>НМТ</tex>, в случае недетерминированного выбора симулирующая машина тоже делает недетерминированный выбор. Сведение совпадает с сведением с предыдущем доказательством.

Теорема о включении BPP в P/poly

2010-04-21T19:22:56Z

Vadim: /* Формулировка */

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

<math>BPP \subset P/poly</math>

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

Для доказательства данной теоремы воспользуемся сильным определением <math> BPP </math>.

Теорема о включении BPP в P/poly

2010-04-21T19:20:19Z

Vadim: Новая страница: «== Формулировка == <math>BPP \subset P/poly</math>»

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

<math>BPP \subset P/poly</math>

Теория сложности (старая трешовая версия)

2010-04-21T19:16:52Z

Vadim: /* Лекция 8 */

== Лекция 1 ==
*[[Класс DSPACE]]
*[[Класс DTIME]]
*[[Теорема о емкостной иерархии]]
*[[Теорема о временной иерархии]]
*[[Сведение по Карпу]]
*[[Сведение по Куку]]
*[[Класс P]]
*[[Класс NP]]
*[[Класс coNP]]

== Практика 1 ==
*[[Сведение по Куку задачи факторизации к языку из NP]]

== Лекция 2 ==
*[[Теорема Кука]]

== Практика 2 ==
*[[Понятие NP-трудной и NP-полной задачи]]
*[[NP-полнота задачи BH1N]]
*[[NP-полнота задачи о выполнимости булевой формулы в форме КНФ]]
*[[NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]]
*[[NP-полнота задачи о клике]]
*[[NP-полнота задачи о независимом множестве]]
*[[NP-полнота задачи о вершинном покрытии]]

== Лекция 3 ==
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бейкера-Гилла-Соловэя]]

== Практика 3 ==
*[[NP-полнота задач о гамильтоновом цикле и пути в графах]]
*[[NP-полнота задачи о сумме подмножества]]
*[[NP-полнота задачи о рюкзаке]]

== Практика, которой на самом деле не было ==
*[[NP-полнота задачи о раскраске графа]]

== Лекция 4 ==
*[[Класс PS]]
*[[Теорема Сэвича]]
*[[PS-полнота задачи Generalized geography]]

== Лекция 6 ==
*Классы [[L]], [[NL]], [[NL-полнота|NLC]]
*[[NL-полнота задачи о достижимости в графе]]
*[[Классы EXP, NEXP. Полнота языков EXP и NEXP]]
*[[Теорема о связи вопросов EXP=NEXP и P=NP]]
*[[Теорема Иммермана]]

== Практика 6 ==
*[[Классы Sigma_i и Pi_i]]
*[[Класс PH]]
*[[Полиномиальная иерархия]]
*[[Теоремы о коллапсе полиномиальной иерархии]]

== Лекция 7 ==
*[[Теорема Карпа-Липтона]]

== Практика 7 ==
*[[Вероятностная машина Тьюринга]]
*[[Класс ZPP]]
*[[Сложностные классы RP и coRP]]
*[[Сложностный класс PP]]
*[[Сложностный класс BPP]]
*[[Уменьшение ошибки в классе RP, сильное и слабое определение]]

== Лекция 8 ==
*[[Теорема о включении BPP в P/poly]]
*[[Теорема Лаутемана]]

== Практика 8 ==
*[[Лемма Шварца-Зиппеля]]

== Лекция 9 ==
*[[Sharp SAT|#SAT]]

Классы EXP, NEXP. Полнота языков EXP и NEXP

2010-04-07T20:58:32Z

Vadim: Новая страница: «== Определение == <math>EXP = \bigcup^{\infty}_{i=0}DTIME(2^{n^{i}})</math> <math>NEXP = \bigcup^{\infty}_{i=0}NTIME(2^{n^{i}})</math> == Полнот…»

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

<math>EXP = \bigcup^{\infty}_{i=0}DTIME(2^{n^{i}})</math>

<math>NEXP = \bigcup^{\infty}_{i=0}NTIME(2^{n^{i}})</math>

== Полнота класса ''EXP'' ==

=== Существует полная в ''EXP'' задача ===
====Доказательство====

Полной задачей в <tex>EXP</tex> является задача <tex>BH_{2,D}</tex>(binary deterministic bounded halt):
<tex>BH_{2,D} =\{ <m, x, t> \mid m(x) = 1, T(m,x) \le t \}</tex>

(<tex>t</tex> задаётся двоичной записью, <tex>m</tex> - детерминированная машина Тьюринга)

Докажем, что <tex>BH_{2,D} \in EXP</tex>. Симулируем работу детерминированной машины <tex>m</tex>. Для этого потребуется время порядка <tex>t^{2}</tex>, но <tex>t \le 2^{|t|} \le 2^{|<m,x,t>|}</tex>. Таким образом, общее время работы <tex>T \le (2^{|<m,x,t>|})^{2} = 2^{2n}</tex> и <tex>BH_{2,D} \in EXP</tex>.
Докажем, что любая задача из <tex>EXP</tex> сводится к <tex>BH_{2,D}</tex>. Пусть <tex>L \in EXP, MT\enskip m</tex>, допускающая язык <tex>L</tex>, работает за время <tex>T \le 2^{p(n)}</tex>, где <tex>p(n)</tex> - полином. Рассмотрим <tex>f : x \rightarrow <m,x,2^{p(n)}></tex> - функция сведения. Чтобы выписать свой результат на ленту ей потребуется полиномиальное от <tex>n</tex> число шагов, так как запись <tex>m</tex> имеет константную длину, <tex>|x| = n</tex> и запись числа <tex>2^{p(n)}</tex> имеет длину порядка <tex>p(n)</tex> в двоичной системе.

== Полнота класса ''NEXP'' ==

=== Существует полная в ''NEXP'' задача ===
====Доказательство====

Полной задачей в <tex>NEXP</tex> является задача <tex>BH_{2,N}</tex>(binary nondeterministic bounded halt):
<tex>BH_{2,N} =\{ <m, x, t> \mid m(x) = 1, T(m,x) \le t \}</tex>

(<tex>t</tex> задаётся двоичной записью, <tex>m</tex> - недетерминированная машина Тьюринга)

Доказательство того, что <tex>BH_{2,N}</tex> - полная задача в <tex>NEXP</tex>, аналогично предыдушему доказательству. Заметим, что при симуляции работы <tex>НМТ</tex>, в случае недетерминированного выбора симулирующая машина тоже делает недетерминированный выбор. Сведение совпадает с сведением с предыдущем доказательством.

Теория сложности (старая трешовая версия)

2010-04-07T19:34:16Z

Vadim: /* Лекция 6 */

== Лекция 1 ==
*[[Класс DSPACE]]
*[[Класс DTIME]]
*[[Теорема о емкостной иерархии]]
*[[Теорема о временной иерархии]]
*[[Сведение по Карпу]]
*[[Сведение по Куку]]
*[[Класс P]]
*[[Класс NP]]
*[[Класс coNP]]

== Практика 1 ==
*[[Сведение по Куку задачи факторизации к языку из NP]]

== Лекция 2 ==
*[[Теорема Кука]]

== Практика 2 ==
*[[Понятие NP-трудной и NP-полной задачи]]
*[[NP-полнота задачи BH1N]]
*[[NP-полнота задачи о выполнимости булевой формулы в форме КНФ]]
*[[NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]]
*[[NP-полнота задачи о клике]]
*[[NP-полнота задачи о независимом множестве]]
*[[NP-полнота задачи о вершинном покрытии]]

== Лекция 3 ==
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бейкера-Гилла-Соловэя]]

== Практика 3 ==
*[[NP-полнота задач о гамильтоновом цикле и пути в графах]]
*[[NP-полнота задачи о сумме подмножества]]
*[[NP-полнота задачи о рюкзаке]]

== Практика, которой на самом деле не было ==
*[[NP-полнота задачи о раскраске графа]]

== Лекция 4 ==
*[[Класс PS]]
*[[Теорема Сэвича]]
*[[PS-полнота задачи Generalized geography]]

== Лекция 6 ==
*[[NL-полнота задачи о достижимости в графе]]
*[[Классы EXP, NEXP. Полнота языков EXP и NEXP]]
*[[Теорема о связи вопросов EXP=NEXP и P=NP]]
*[[Теорема Иммермана]]

== Практика 6 ==
*[[Классы Sigma_i и Pi_i]]
*[[Класс PH]]
*[[Полиномиальная иерархия]]
*[[Теоремы о коллапсе полиномиальной иерархии]]

== Практика 7 ==
*[[Класс BPP]]