Семинар 11. NP-задачи

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

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

Доказательство NP-полноты проверки наличия гамильтонова пути/цикла, через сведение CNF-SAT к этой задаче. Построение графа: переменные-ромбы, значение переменной и направление хода, вершины-термы и рёбра отвлечения. Путь <=> разрешимость.

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