В теории сложности вычислений NP-трудность ( недетерминированная полиномиальная трудность по времени) является определяющим свойством класса задач, которые неформально «по крайней мере так же сложны, как самые сложные проблемы в NP » . Простым примером NP-трудной задачи является задача о сумме подмножеств .
Более точная спецификация такова: проблема H является NP-трудной, когда каждую задачу L из NP можно свести за полиномиальное время к H ; то есть, если предположить, что решение H занимает 1 единицу времени, решение H можно использовать для решения L за полиномиальное время. [1] [2] Как следствие, поиск алгоритма с полиномиальным временем для решения любой NP-сложной проблемы даст алгоритмы с полиномиальным временем для всех проблем в NP. Поскольку предполагается, что P≠NP , маловероятно, что такой алгоритм существует. [3]
Предполагается, что для решения NP-трудных задач не существует алгоритмов с полиномиальным временем, но это не доказано. [4] Более того, класс 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 ).
Все NP-полные задачи также являются NP-сложными (см. Список NP-полных задач ). Например, задача оптимизации поиска циклического маршрута с наименьшей стоимостью через все узлы взвешенного графа, широко известная как задача коммивояжера , является NP-трудной. [6] Еще одним примером является проблема с суммой подмножеств : для данного набора целых чисел, любое их непустое подмножество в сумме дает ноль? Это проблема принятия решения , и она оказывается NP-полной.
Существуют задачи принятия решения, которые являются NP-сложными , но не NP-полными, например проблема остановки . Это проблема, которая спрашивает: «Для данной программы и ее ввода будет ли она работать вечно?» Это вопрос «да / нет» , как и проблема принятия решения. Легко доказать, что проблема остановки NP-трудна, но не NP-полна. Например, проблему логической выполнимости можно свести к проблеме остановки, преобразовав ее в описание машины Тьюринга , которая пробует все присваивания значений истинности и когда находит такое, которое удовлетворяет формуле, она останавливается, а в противном случае переходит в бесконечный цикл. Также легко видеть, что проблема остановки не относится к NP , поскольку все проблемы в NP разрешимы за конечное число операций, но проблема остановки, вообще говоря, неразрешима . Существуют также NP-сложные задачи, которые не являются ни NP-полными , ни неразрешимыми . Например, язык истинных количественных булевых формул разрешим в полиномиальном пространстве , но не в недетерминированном полиномиальном времени (если только NP = PSPACE ). [7]
NP-сложные задачи не обязательно должны быть элементами класса сложности NP. Поскольку NP играет центральную роль в вычислительной сложности , он используется в качестве основы нескольких классов:
NP-сложные проблемы часто решаются с помощью языков, основанных на правилах, в таких областях, как: