Список пройденных тем.

1. О-большое и о-малое символики. Полиномиальные и экспоненциальные асимптотические оценки. Временная сложность МТ. Сложность языка { 0ⁿ1ⁿ }. Зависимость определения сложности от алгоритмической модели. Оценка сложности эмуляции многоленточной МТ на одноленточной. Классы TIME(t(n)).
2. Оценка сложности эмуляции недетерминированной МТ на детерминированной. Понятие полиномиальной сложности: класс P. Инвариантность класса P относительно выбора детерминированной алгоритмической модели. Примеры языков из P: поиск пути в графе, проверка на относительную простоту, проверка принадлежности строки КС-языку.
3. Поиск гамильтонова пути в графе, проблема HAMPATH. Понятие алгоритма проверки. Проблема разложения числа на множители. Полиномиальные алгоритмы проверки, определение класса NP. Критерий принадлежности языка классу NP. Классы NTIME(t(n)). NP ⊂ EXPTIME. (mkv/theora, 439 МБ torrent/ftp.)
4. Проблема выполнимости (SAT). КНФ и 3-КНФ, проблема 3SAT. Полиномиальная редукция. 3SAT ≤_P CLIQUE. Понятие NP-полноты. Вопрос P ≠ NP. Критерий NP-полноты при наличии одной NP-полной проблемы. Теорема Кука-Левина о NP-полноте проблемы SAT: план доказательства. (mkv/theora, 562 МБ torrent/ftp.)
5. Теорема Кука-Левина: доказательство. NP-полнота проблемы 3SAT. CLIQUE — NP-полная. NP-полнота проблемы вершинного покрытия (3SAT ≤_P VERTEX-COVER). (mkv/theora, 765 МБ torrent/ftp.)
6. NP-полнота проблем HAMPATH и UHAMPATH (3SAT ≤_P HAMPATH ≤_P UHAMPATH), а также проблемы SUBSET-SUM.
7. Сложность по памяти. Классы PSPACE и NPSPACE. Примеры: SAT ∈ PSPACE, ALL_NFA ∈ NPSPACE. Теорема Савича. PSPACE = NPSPACE ⊂ EXPTIME. (mkv/theora, 510 МБ torrent/ftp.)
8. Понятие PSPACE-полноты относительно полиномиальной редукции. PSPACE-полнота проблемы TQBF. Выиграшные стратегии в играх. Игра в формулы. Обобщенная игра в города. Кошки-мышки (не PSPACE-полная).
9. PSPACE-полнота проблемы GG — поиска выигрышной стратегии обобщенной игры в города (TQBF ≤_P GG). Понятие логарифмической сложности по памяти. МТ с дополнительной лентой только для чтения. Корректировка доказательства теоремы Савича для проблем с сублинейной сложностью по памяти. Классы L и NL. Примеры: { 0ⁿ1ⁿ } ∈ L, PATH ∈ NL. (mkv/theora, 567 МБ torrent/ftp.)
10. Преобразователь с логарифмической памятью (трехленточный). Логарифмическая (по памяти) сводимость. Понятие NL-полноты относительно логарифмической сводимости. NL-полнота проблемы PATH. Классы NL и coNL. (mkv/theora, 391 МБ torrent/ftp.)
11. PATH ∈ NL. NL = coNL. PSPACE-полнота проблемы TQBF относительно логарифмической сводимости.
12. Труднорешаемые задачи. Конструируемые по памяти функции. Теорема об иерархии по памяти. Метод диагонализации. Следствия. Конструируемые по времени функции. Теорема об иерархии по времени. Следствия.
13. Алгоритмы, требующие экспоненциальную память. Регулярные выражения. EXPSPACE-полнота проблемы EQ_REX↑.