Сводимость по Карпу¶

Сводимость по Карпу (также известная как «многозначная сводимость» или «полиномиальная сводимость по Карпу») — это понятие в теории алгоритмов и теории сложности вычислений, определяющее отношение между двумя задачами разрешения. Задача A сводится по Карпу к задаче B, если существует детерминированная машина Тьюринга с полиномиальным временем работы, которая преобразует любой вход задачи A во вход задачи B таким образом, что ответы на оба входа совпадают.

¶Определение

Формально, задача A сводится по Карпу к задаче B (обозначается A ≤p B), если существует функция f, вычислимая за полиномиальное время, такая что для любого слова x:

• x ∈ A тогда и только тогда, когда f(x) ∈ B.

Функция f называется сводящей функцией. Ключевое требование — время вычисления f ограничено полиномом от длины входа |x|.

Сводимость по Карпу была предложена американским учёным Ричардом Карпом в 1972 году в его знаменитой работе «Reducibility Among Combinatorial Problems». Это понятие стало развитием идей Стивена Кука, который годом ранее ввёл понятие NP-полноты, используя более слабую сводимость по Куку (полиномиальную сводимость по Тьюрингу).

¶Свойства

Сводимость по Карпу обладает следующими важными свойствами:

• Рефлексивность: любая задача сводима к самой себе (f — тождественная функция).
• Транзитивность: если A ≤p B и B ≤p C, то A ≤p C.
• Замкнутость классов: если A ≤p B и B ∈ P, то A ∈ P; если A ≤p B и B ∈ NP, то A ∈ NP.

Отношение ≤p задаёт на множестве задач предпорядок. Задачи, сводимые друг к другу в обе стороны, называются эквивалентными по Карпу.

¶Отличие от сводимости по Куку

Сводимость по Куку (полиномиальная сводимость по Тьюрингу) позволяет задавать задаче B произвольное число вопросов, причём каждый следующий вопрос может зависеть от предыдущих ответов. Сводимость по Карпу является частным случаем сводимости по Куку: она допускает только один вопрос к B, причём ответ на него должен совпадать с ответом на исходный вход. Сводимость по Карпу строго сильнее: если A ≤p B, то A сводима по Куку к B, но обратное не всегда верно.

¶Роль в теории NP-полноты

Сводимость по Карпу является стандартным инструментом для доказательства NP-полноты задач. Задача называется NP-трудной, если к ней сводится по Карпу любая задача из класса NP. Задача называется NP-полной, если она одновременно принадлежит классу NP и является NP-трудной.

Для доказательства NP-полноты новой задачи C используется следующий приём: берётся известная NP-полная задача (например, задача выполнимости булевых формул SAT), строится полиномиальная сводимость SAT ≤p C, и показывается, что C ∈ NP. После этого C объявляется NP-полной.

В своей работе 1972 года Карп представил список из 21 комбинаторной задачи (включая задачу о клике, задачу о вершинном покрытии, задачу о гамильтоновом цикле, задачу о сумме подмножества и другие), для которых он построил цепочки сводимостей, доказав их NP-полноту.

¶Примеры сводимостей

Классическим примером является сведение задачи о выполнимости булевой формулы (SAT) к задаче о 3-выполнимости (3-SAT). Каждая формула преобразуется в эквивалентную 3-КНФ-формулу за полиномиальное время, что доказывает NP-полноту 3-SAT.

Другой пример — сведение задачи о 3-выполнимости к задаче о клике. По формуле в 3-КНФ строится граф, в котором клика размера, равного числу дизъюнктов, существует тогда и только тогда, когда формула выполнима.

¶Значение и критика

Сводимость по Карпу стала основным инструментом классификации вычислительных задач. Она позволяет устанавливать относительную сложность задач без точного знания их абсолютной сложности. Однако сводимость по Карпу чувствительна к деталям кодирования входных данных: изменение кодировки может повлиять на существование полиномиальной сводимости. Кроме того, для некоторых задач (например, задач оптимизации) применяются более специализированные виды сводимостей, такие как сводимость, сохраняющая приближение.