В теории вычислительной сложности вычислительная задача H называется NP-трудной , если для каждой задачи L , которая может быть решена за недетерминированное полиномиальное время , существует полиномиальное сокращение от L до H. То есть, предполагая, что решение для H занимает 1 единицу времени, решение H может быть использовано для решения L за полиномиальное время. [1] [2] Как следствие, нахождение алгоритма полиномиального времени для решения одной NP-трудной задачи даст алгоритмы полиномиального времени для всех задач в классе сложности NP . Поскольку предполагается, но не доказано, что P≠NP , маловероятно, что существуют какие-либо полиномиальные алгоритмы для NP-трудных задач. [3] [4]
Простым примером NP-трудной задачи является задача о сумме подмножеств .
Неформально, если H является NP-трудной, то она по крайней мере так же сложна для решения, как и проблемы в NP . Однако обратное неверно: некоторые проблемы неразрешимы , и поэтому их даже сложнее решить, чем все проблемы в NP, но они, вероятно, не являются NP-трудными (если только P=NP). [5]
Задача принятия решений H является NP-трудной, когда для каждой задачи L из NP существует многоединичное сведение от L к H за полиномиальное время . [1] : 80
Другое определение требует, чтобы существовало полиномиальное время сведения от NP -полной задачи G к H. [1] : 91 Поскольку любая задача L из NP сводится за полиномиальное время к G , L в свою очередь сводится к H за полиномиальное время, так что это новое определение подразумевает предыдущее. Оно не ограничивает класс NP-трудных задачами принятия решений, а также включает задачи поиска или задачи оптимизации .
Если P ≠ NP, то NP-трудные задачи не могут быть решены за полиномиальное время.
Некоторые NP-трудные задачи оптимизации могут быть аппроксимированы за полиномиальное время до некоторого постоянного коэффициента аппроксимации (в частности, в APX ) или даже до любого коэффициента аппроксимации (в PTAS или FPTAS ). Существует много классов аппроксимируемости, каждый из которых позволяет аппроксимировать до разного уровня. [6]
Все NP-полные задачи также являются NP-трудными (см. Список NP-полных задач ). Например, задача оптимизации поиска циклического маршрута с наименьшей стоимостью через все узлы взвешенного графа — обычно известная как задача коммивояжера — является NP-трудной. [7] Задача о сумме подмножеств — еще один пример: дано множество целых чисел, дает ли какое-либо непустое подмножество из них в сумме ноль? Это задача принятия решений , и она оказывается NP-полной.
Существуют проблемы принятия решений, которые являются NP-трудными , но не NP-полными, такие как проблема остановки . Это проблема, которая спрашивает «при заданной программе и ее входных данных она будет работать вечно?» Это вопрос типа «да / нет » , и поэтому это проблема принятия решений. Легко доказать, что проблема остановки является NP-трудной, но не NP-полной. Например, проблему выполнимости булевых значений можно свести к проблеме остановки, преобразовав ее в описание машины Тьюринга , которая пробует все назначения истинностных значений , и когда она находит то, которое удовлетворяет формуле, она останавливается, а в противном случае она переходит в бесконечный цикл. Также легко увидеть, что проблема остановки не принадлежит NP, поскольку все проблемы в NP разрешимы за конечное число операций, но проблема остановки, в общем случае, неразрешима . Существуют также NP-трудные проблемы, которые не являются ни NP-полными , ни неразрешимыми . Например, язык истинных квантифицированных булевых формул разрешим в полиномиальном пространстве , но не за недетерминированное полиномиальное время (если только NP = PSPACE ). [8]
NP-трудные задачи не обязательно должны быть элементами класса сложности NP. Поскольку NP играет центральную роль в вычислительной сложности , он используется в качестве основы нескольких классов:
NP-трудные задачи часто решаются с помощью языков, основанных на правилах, в таких областях, как: