NP-трудная задача

NP-трудная задача — это задача из класса NP (недетерминированно полиномиальных), к которой могут быть сведены (полиномиально по времени) любые другие задачи из класса NP. Иными словами, NP-трудная задача является «не менее сложной», чем любая задача из NP. Если для какой-либо NP-трудной задачи удастся найти полиномиальный алгоритм решения, то это автоматически даст полиномиальные алгоритмы для всех задач из NP, что равносильно доказательству равенства классов P и NP (P = NP). В отличие от NP-полных задач, NP-трудные задачи не обязательно сами принадлежат классу NP (то есть их решение может не проверяться за полиномиальное время).

Определение и формальная основа

Формально задача \( L \) называется NP-трудной, если для любой задачи \( L' \in NP \) существует полиномиальное сведение (по Карпу) \( L' \leq_p L \). Это означает, что существует алгоритм, работающий за полиномиальное время, который преобразует любой экземпляр задачи \( L' \) в экземпляр задачи \( L \) так, что ответы на них совпадают. Если такое сведение существует, то решение \( L \) за полиномиальное время влечёт за собой решение \( L' \) за полиномиальное время.

Класс NP-трудных задач включает в себя NP-полные задачи (которые одновременно являются NP-трудными и принадлежат NP), а также задачи, которые «сложнее» NP, например, задачи, разрешимые только за экспоненциальное время, или задачи, не входящие в NP (например, задачи, требующие перебора всех возможных решений, или задачи, не имеющие полиномиальной верификации).

История

Понятие NP-трудности возникло в начале 1970-х годов в рамках теории сложности вычислений. Ключевую роль сыграли работы Стивена Кука (1971) и Ричарда Карпа (1972). Кук доказал, что задача выполнимости булевой формулы (SAT) является NP-полной, то есть она принадлежит NP и к ней сводятся все задачи из NP. Карп расширил этот результат, показав NP-полноту для 21 классической задачи, включая задачу о коммивояжёре, задачу о рюкзаке, задачу о раскраске графа и другие. Эти работы заложили фундамент для понимания того, что многие практически важные задачи не имеют эффективных (полиномиальных) алгоритмов в общем случае, если P ≠ NP.

Соотношение с классами P и NP

Основной вопрос теории сложности — равенство классов P и NP. Если P = NP, то все NP-трудные задачи, принадлежащие NP (то есть NP-полные), будут решаться за полиномиальное время. Если же P ≠ NP, то ни одна NP-трудная задача не может быть решена за полиномиальное время. Для NP-трудных задач, не входящих в NP, даже при P = NP полиномиальное решение может не существовать — они могут оставаться экспоненциально сложными.

Примеры NP-трудных задач

NP-полные задачи (принадлежат NP)

• Задача выполнимости булевой формулы (SAT) — определение, существует ли набор логических переменных, при котором заданная булева формула принимает значение «истина».
• Задача о коммивояжёре (TSP) — нахождение кратчайшего маршрута, проходящего через все заданные города ровно по одному разу и возвращающегося в начальный город. В общей постановке (с произвольными расстояниями) является NP-трудной и NP-полной для евклидовой метрики.
• Задача о рюкзаке — выбор подмножества предметов с заданными весами и стоимостями, укладывающихся в рюкзак ограниченной вместимости, с максимальной суммарной стоимостью.
• Задача о вершинном покрытии — нахождение минимального множества вершин графа, покрывающего все его рёбра.
• Задача о клике — определение, содержит ли граф полный подграф заданного размера.
• Задача о раскраске графа — определение минимального числа цветов, необходимых для раскраски вершин графа так, чтобы смежные вершины имели разные цвета. Для трёх цветов задача является NP-полной.
• Задача о сумме подмножеств — определение, существует ли подмножество заданного множества чисел, сумма которых равна заданному значению.

NP-трудные задачи, не принадлежащие NP

• Задача остановки (halting problem) — определение, завершится ли выполнение произвольной программы на данном входе за конечное время. Эта задача неразрешима (не имеет алгоритма вообще), но является NP-трудной, так как к ней можно свести любую задачу из NP.
• Задача о выполнимости кванторной булевой формулы (QBF-SAT) — определение истинности булевой формулы с кванторами существования и всеобщности. Эта задача является PSPACE-полной и, как считается, сложнее NP-полных задач.
• Задача о поиске кратчайшего пути в графе с отрицательными циклами — если в графе есть отрицательные циклы, задача поиска кратчайшего пути становится NP-трудной, так как требует обнаружения циклов и их обхода.
• Задача о максимальном разрезе — нахождение разбиения вершин графа на два подмножества, максимизирующего количество рёбер между ними. В общем случае NP-трудная, но не входит в NP, так как не имеет полиномиальной верификации (оптимум не проверяется за полиномиальное время).

Методы решения NP-трудных задач

Поскольку точное решение NP-трудных задач в общем случае требует экспоненциального времени (если P ≠ NP), на практике применяются следующие подходы:

• Приближённые алгоритмы — алгоритмы, гарантирующие нахождение решения, близкого к оптимальному, с известной оценкой погрешности (например, для задачи о вершинном покрытии существует 2-приближённый алгоритм).
• Эвристические методы — алгоритмы, не дающие гарантий качества, но работающие на практике (например, генетические алгоритмы, имитация отжига, муравьиные алгоритмы).
• Методы ветвей и границ — точные алгоритмы, использующие отсечение неперспективных ветвей перебора, часто применяемые для задач небольшой размерности.
• Сведение к SAT — многие задачи могут быть преобразованы в задачу SAT, для которой существуют эффективные решатели (SAT-солверы), работающие на многих практических примерах.
• Параметризованная сложность — если задача имеет малый параметр (например, размер искомого решения), можно получить алгоритмы, экспоненциальные по параметру, но полиномиальные по размеру входа.

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

NP-трудные задачи имеют огромное практическое значение: к ним относятся задачи оптимизации в логистике, планировании, биоинформатике, криптографии, искусственном интеллекте и многих других областях. Понимание NP-трудности позволяет оценить принципиальную сложность задачи и выбрать подходящий метод решения.

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

Источники

• Стивен Кук, «The complexity of theorem-proving procedures», 1971.
• Ричард Карп, «Reducibility among combinatorial problems», 1972.
• Майкл Гэри, Дэвид Джонсон, «Computers and Intractability: A Guide to the Theory of NP-Completeness», 1979.
• Кристофер Мур, Стефан Мертенс, «The Nature of Computation», 2011.
• Санжей Арора, Боаз Барак, «Computational Complexity: A Modern Approach», 2009.