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

Лекция 1. Вводная

Начнем курс с введения понятий DTIME и DSPACE.

• DTIME(f(n)) = [math]\{ L \mid \exists [/math] машина Тьюринга [math]m : L(m)=L, Time(m,x) \le f(|x|) \}[/math], где [math]|x|[/math] — длина входа [math]x[/math].

• DSPACE(f(n)) = [math]\{ L \mid \exists [/math] машина Тьюринга [math]m : L(m)=L, Space(m,x) \le f(|x|) \}[/math].

Аналогичным образом введем классы NSPACE и NTIME, использующие недетерминированную машину Тьюринга взамен детерминированной (в течении всего курса префикс D соответствует детерминизму, а N — недетерминизму).

Рассмотрим и докажем теоремы о емкостной и временной иерархии.

• Теорема о емкостной иерархии утверждает, что для любых двух конструируемых по памяти функций [math]f[/math] и [math]g[/math] таких, что [math] \lim \limits_{n \rightarrow \infty} f(n)/g(n) = 0[/math], выполняется DSPACE(g(n)) ≠ DSPACE(f(n)).

• Теорема о временной иерархии утверждает, что для любых двух конструируемых по времени функций [math]f\,\![/math] и [math]g\,\![/math] таких, что [math] \lim \limits_{n \rightarrow \infty} \frac{t(f(n))}{g(n)} = 0[/math], выполняется DTIME(g(n)) ≠ DTIME(f(n)).

---

Через понятия классов DSPACE, DTIME, NSPACE и NTIME будет дано определение многим сложностным классам, в том числе P и NP.

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

• P=[math]\bigcup_{i=0}^{\infty}[/math]DTIME[math](in^i)[/math]

В свою очередь, при разрешении языка из класса NP используется недетерминированная машина:

• NP=[math]\bigcup_{i=0}^{\infty}[/math] NTIME[math](in^i)[/math]

Дадим определение класса NP на языке сертификатов:

• NP=[math]\Sigma_1 = \{L|\exists R(x,y) \in P, p \in Poly | l \in L \Leftrightarrow \exists y, |y| \le p(x) | R(x,y)=1\}[/math] (первое равенство доказывается в статье NP). Поясним, что [math]y[/math] является сертификатом принадлежности [math]x[/math] языку [math]L[/math], если существует полиномиальное отношение (верификатор) [math]R[/math], такое что [math]R(x,y)=1[/math] тогда и только тогда, когда [math]x[/math] принадлежит [math]L[/math].

Вместе со многими сложностными классами имеет смысл рассматривать и их дополнения (используется приставка co-). Например, класс co-NP.

---

Введем в рассмотрение отношения между языками: сведение по Карпу и сведение по Куку.

• Язык [math]A[/math] сводится по Карпу к языку [math]B[/math], если существует функция [math]f(x)[/math] такая, что [math]x \in A[/math] тогда и только тогда, когда [math]f(x) \in B[/math].
• Язык [math]A[/math] сводится по Куку к [math]B[/math], если существует разрешающая язык [math]A[/math] программа [math]m[/math], работающая полиномиальное время от длины входа, которая может использовать разрешающую программу [math]m_B[/math] для языка [math]B[/math] в качестве оракула. При этом время работы [math]m_B[/math] не учитывается.

В дальнейшем чаще будет рассматриваться сведение по Карпу.

Практика 1

• Сведение по Куку задачи факторизации к языку из NP

Лекция 2

• Теорема Кука

Практика 2

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

Лекция 3

• Теорема Ладнера
• Теорема Левина
• Теорема Бейкера-Гилла-Соловэя

Практика 3

• NP-полнота задач о гамильтоновом цикле и пути в графах
• NP-полнота задачи о сумме подмножества
• NP-полнота задачи о рюкзаке

Практика, которой на самом деле не было

• NP-полнота задачи о раскраске графа

Лекция 4

• Схемная сложность
• P/poly
• Редкие языки
• Теорема Махэни

Лекция 5

• Класс PS
• Теорема Сэвича
• PS-полнота задачи Generalized geography

Лекция 6

• Классы L, 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

• Класс IP
• Принадлежность проблемы GNI классу IP
• #SAT

Лекция 10

• Теорема Шамира
• Семейство универсальных попарно независимых хеш-функций
• Протокол Гольдвассера-Сипсера для оценки размера множества
• Теорема Голдвассера, Сипсера

Лекция 11

• Абсолютная секретность
• Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP
• Односторонние функции и псевдослучайные генераторы
• Доказательства с нулевым разглашением

Лекция 12

• Кубит
• Унитарные операторы
• ЭПР парадокс
• Квантовый логический элемент NOT
• Преобразование Адамара
• Квантовый логический элемент CNOT
• Квантовый логический элемент Тоффоли
• Квантовая схема

Лекция 13

• Класс PCP