Применение PCP теоремы к доказательству NP трудности задачи аппроксимации размера максимальной клики с точностью до постоянного множителя.
Теория сложности в среднем: полиномиально моделируемые последовательности распределений, распределенные задачи, классы HeurBPP и (NP,PSamp). Сведения, сохраняющие HeurBPP и (NP,PSamp) полные задачи.
Почему в определении AM[2] и MA[2] можно считать, что прувер доказывает верные факты безошибочно.
Доказательство включения PSPACE в AM (окончание).
Включение MA[2] в AM[2]. Совпадение AM[2] и AM[c] для любого c>1. Включение MA[2] в \Sigma_2 и AM[2] в \Pi_2.
Начало доказательства включения PSPACE в AM.
Еще раз о доказательстве леммы о повторении интерактивного протокола.
Еще раз о IP=AM и увеличение цены игры.
АМ протокол для неизоморфизма графов.
Лемма о параллельном повторении интерактивного протокола.
IP=AM
Лемма о последовательном повторении интерактивного протокола.
Класс АМ (с открытыми бросаниями). Включение IP в PSPACE
Универсальный алгоритм поиска Левина.
Интерактивные доказательства. Классы МА, PCP, PCP с доказательством экспоненциальной длины, IP. Интерактивное доказательство неизоморфности графов.
Окончание доказательства теоремы Тоды: PP^{+P} включено в P^{#P}
Теорема Иммермана: NLOGSPACE=coNLOGSPACE.
Лекции не было.
Релятивизуемость всех до сих пор доказанных теорем. Невозможность релятивизуемого решения проблемы перебора.
Теорема Закоса. Класс +Р и его замкнутость относительно сводимости Кука. Начало доказательства теоремы Тоды: включение PH в BPP^{+P}.
Теорема Вэльянта о #P полноте задачи вычисления перманента булевой матрицы.
Класс #P задач подсчета. Сведение задач из #P к языкам из класса РР и обратное сведение. #P полнота задач подсчета количества выполняющих присваиваний для булевых схем и 3CNF, подсчета количества клик в графе и подсчета количества раскрасок графа в 3 цвета.
Обобщение теоремы Фишера-Рабина на вероятностные машины и альтернирующие машины.
Теорема Вэльянта-Вазирани.
Теорема об иерархии для NP и других классов полиномиальной иерархии.
Характеризация класса PSPACE с помощью полиномиальных игр. PSPACE полнота БФК. PSPACE полнота задачи эквивалентности регулярных выражений. Распознавание s-t-связности на зоне O(\log^2 n)
Класс PSPACE. Вложение PSPACE в EXPTIME. Вложение PH в PSPACE. Полиномиальные игры. Принадлежность PSPACE множетсва выигрышных позиций в полиномиальной игре.
Включение BPP в \Sigma_2.
Вне класса NP: полиномиальная иерархия. Примеры: БФК, жесткие графы, неупрощаемые формулы, единственная наибольшая клика, размер наибольшей клики. Полные проблемы в классах полиномиальной иерархии.
Уменьшение вероятности ошибки при повторении. Классы PP, BPP, FBPP, RP. Включение BPP в P/poly.
Алгоритмические проблемы общего вида. Взаимная сводимость NP задач поиска и NP задач распознавания. Взаимная сводимость NP задач поиска и задач оптимизации.
Приближенное решение задач оптимизации. NP трудность задачи нахождения раскраски графа в (4/3-\eps+o(1))\xi(G) цветов. Полиномиальный алгоритм 7/8-апроксимации MAX3CNF.
Вероятностные полиномиальные алгоритмы. Вычисления с ограниченной ошибкой. Полиномиальный вероятностный алгоритм проверки истинности алгебраического тождества.
NP полнота задач Гамильтонов цикла, 3-раскраска, Коммивояжер.
NP полнота задачи выполнимости 3-КНФ. Полиномиальная разрешимость задач 2-КНФ и 2-раскраска.
NP полнота задач Клика, Независимое множество, Вершинное покрытие, Сумма подмножества.
Класс NP. Сводимость Карпа и ее свойства.
NP трудные и NP полные задачи. Теорема Кука - Левина об NP полноте задачи о выполнимости схем из функциональных элементов.
Класс nuP. Включение P в nuP. Класс P/poly и его совпадение с классом nuP.
Схемы из функциональных элементов. Верхняя оценка O(n2^n) схемной сложности любой булевой функции от n переменных. Существование функций схемной сложности 2^n/3n.
Теорема Фишера - Рабина об экспоненциальной нижней оценке времени распознавания истинности формул первого порядка в аддитивной группе действительных чисел.
Равнодоступные адресные машины (РАМ). Моделирование машин Тьюринга на РАМ и РАМ на машинах Тьюринга. Класс P полиномиально разрешимых языков и машинно-независимость его определения.
Универсальная машина Тьюринга и оценка времени ее работы. Теорема о иерархии по времени.
Моделирование двухленточных машины Тьюринга на одноленточных машинах. Время, достаточное для копирования, сложения, обращения и распознавания палиндромов на одноленточных и двухленточных машинах Тьюринга.
Теорема Хэнни-Стирнза о квадратичной нижней оценке времени решения этих задач на одноленточных машинах Тьюринга.