Семинар 11. NP-задачи и игры на графах

Определение классов P и NP. Пример: решение SAT на недетерминированной машине. Полиномиальная сводимость по Тюрингу. Разбиение NP на классы эквивалентности. Наличие максимального класса NP-complete. Определение NP-hard задачи.

Известные NP-полные задачи: SAT (в т.ч. CNF-SAT и 3-SAT), ILP (в т.ч. BLP), гамильтонов цикл, клика, вершинное покрытие.

Решение 2-SAT. Превращение дизъюнкций в пары импликаций. Граф импликаций, его кососимметричность. Два условия на раскраску вершин. Компоненты сильной связности, условие неразрешимости. Алгоритм построения решения. Доказательство корректности. Время работы O(M+N).

Игра на графе --- общее определение, граф. Ходы и условие проигрыша. Определение проигрышной и выигрышной вершины. Ациклический граф: классификация вершин на выигрышные и проигрышные за O(M + N). Оптимальная стратегия.

Случай графа с циклами. Бесконечная игра и ничья. Классификация вершины на проигрышные, выигрышные и ничейные за O(MN). Оптимальная стратегия. Быстрый алгоритм за O(M + N).