Полиномиальные сведения между SAT, 3-SAT, CLIQUE и другими NP-полными задачами

Полиномиальные сведения используются как цепочка переноса NP-трудности. После теоремы Кука не нужно заново сводить все задачи класса \(NP\) к каждой новой задаче: достаточно построить корректное полиномиальное сведение из уже известной NP-полной задачи.¹

В курсе основная сеть сведений имеет вид: \(SAT\prec3\text{-SAT}\), \(SAT\prec CLIQUE\prec VERTEX\ COVER\prec SET\ COVER\), а также \(3\text{-SAT}\prec COLORING\) и \(SAT\prec0\text{-}1\text{ ЦП}\).¹

Что важно запомнить

Направление сведения всегда идёт от уже известной трудной задачи к задаче, чью трудность требуется доказать.
Каждое сведение должно сохранять ответ «да/нет» и вычисляться за полиномиальное время.
Транзитивность позволяет соединять локальные конструкции в длинные цепочки.
Для NP-полноты одной NP-трудности недостаточно: целевая задача также должна принадлежать \(NP\).

Карта конкретных сведений курса

Сведение	Ключевая конструкция
\(SAT\prec3\text{-SAT}\)	Длинная скобка дробится с помощью новых переменных на скобки длины не более 3.
\(SAT\prec0\text{-}1\text{ ЦП}\)	Каждая скобка КНФ превращается в линейное неравенство над бинарными переменными.
\(SAT\prec CLIQUE\)	Создаются вершины-литералы по скобкам. Рёбра соединяют совместимые литералы из разных скобок.
\(CLIQUE\prec VERTEX\ COVER\)	Переход к дополнительному графу и параметру \(l=\|V\|-k\).
\(VERTEX\ COVER\prec SET\ COVER\)	Универсум — рёбра графа. Каждой вершине соответствует множество инцидентных рёбер.
\(3\text{-SAT}\prec COLORING\)	Строится граф с вершинами переменных, их отрицаний, опорными вершинами и вершинами скобок. Специальный цвет кодирует присваивание.

Все эти конструкции приведены в пособии Сапоженко как последовательное расширение списка NP-полных задач.¹

Как читать цепочку

Например, после доказательства NP-полноты SAT и построения \(SAT\prec CLIQUE\) задача CLIQUE становится NP-трудной. После построения \(CLIQUE\prec VERTEX\ COVER\) транзитивность даёт \(SAT\prec VERTEX\ COVER\), а затем через \(VERTEX\ COVER\prec SET\ COVER\) — трудность SET COVER.

Ключевой объект в каждом звене — не название задачи, а отображение экземпляров: что именно строится, почему положительный экземпляр переходит в положительный и отрицательный — в отрицательный, и почему размер результата остаётся полиномиальным.

Частые ошибки

Переворачивать стрелку сведения. Если нужно доказать трудность задачи \(B\), строят \(A\prec B\) из уже известной трудной \(A\).
Перечислять цепочку без конструкции экземпляра. На экзамене важно объяснить, что именно преобразуется и почему сохраняется ответ.
Считать транзитивность достаточной для NP-полноты без проверки \(B\in NP\).

Другие вопросы

Источники

1 Сапоженко А. А. Некоторые вопросы сложности алгоритмов М.: МГУ, факультет ВМК, 2001 г., §§5–6: 3-ВЫП и схема сведений между 0–1 ЦЛП, КЛИКА, ВЕРШИННОЕ ПОКРЫТИЕ, ПОКРЫТИЕ МНОЖЕСТВ, РАСКРАСКА