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

Лекция 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, 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

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