Спецкурс Введение в структурную теорию сложности

СПб.: Санкт-Петербургский государственный университет; Санкт-Петербургское отделение Математического института им. В.А.Стеклова (ПОМИ) РАН, Гирш Э.А., 2002 г. Спецкурс прочитан в Санкт-Петербургском государственном университете в 2002 г. Материал включает в себя конспекты 14 лекций по указанному спецкурсу. Задачи поиска. Классы P и NP. СведЕния. NP-полные задачи.
Оптимальный алгоритм для NP-задачи…
Иерархия по памяти.
Сложность недетерминированных вычислений по памяти.
Полиномиальная иерархия.
Вероятностные алгоритмы. Булевы схемы.
Лемма Вэлиента-Вазирани.
Теорема Тода (1 часть).
Теорема Тода (2 часть).
Параллельные вычисления.
Уменьшение вероятности ошибки алгоритма из BPP с использованием небольшого количества случайных битов.
Схемная сложность классов полиномиальной иерархии.
Иерархия для эвристических вероятностных вычислений.