#дневниклекций
Вчера была первая лекция про NP-полноту - центральную тему первой части курса. Изучили следующее:
- Полиномиальная сводимость (по Карпу) и её основные свойства
- Определение NP-трудности и NP-полноты. Получение новых NP-трудных и NP-полных задач через сводимость
- Общая картина NP-полных, NP-трудных и NP-промежуточных задач. Теорема Ладнера (б/д)
- Генерическая NP-полная задача и доказательство, что она действительно NP-полная
- Задачи SAT и 3SAT, а также CSP и qCSP. Сводимости 3COL к 4CSP и SAT к 3SAT
- Теорема Кука-Левина: формулировка, построение таблицы по одноленточной машине Тьюринга, построение формул, выражающих корректность начальной конфигурации, итоговое принимающее состояние и корректность всех переходов (последняя - через идею локальности вычислений). Итоговая компоновка доказательства теоремы из этих компонентов.