Войти
диаграмма Эйлера для P, NP, NP-полного и NP-жесткого набора задач. Левая часть действительна при предположении, что P ≠ NP, а правая часть действительна при предположении, что P = NP (за исключением того, что пустой язык и его дополнение никогда не являются NP-полными) В теории вычислительной сложности, NP-твердость (недетерминированная полиномиальная временная твердость) является определяющим свойством класса задач, которые неформально "по крайней мере как сложнейшие проблемы в НП ». Простым примером NP-трудной задачи является задача о сумме подмножеств.
Более точная спецификация: задача H является NP-сложной, когда каждая проблема L в NP может быть сокращена в полиномиальное время до H; то есть, предполагая, что решение для H занимает 1 единицу времени, решение H можно использовать для решения L за полиномиальное время. Как следствие, поиск алгоритма с полиномиальным временем для решения любой NP-трудной задачи даст алгоритмы с полиномиальным временем для всех проблем в NP. Поскольку есть подозрение, что P 
Распространенным заблуждением является то, что NP в "NP-hard "означает" неполиномиальные ", тогда как на самом деле это означает" недетерминированные полиномиальные приемлемые задачи ". Есть подозрение, что не существует алгоритмов с полиномиальным временем для NP-сложных задач, но это не было доказано. Более того, класс P, в котором все задачи могут быть решены за полиномиальное время, содержится в классе NP.
A проблема решения H является NP-трудным, когда для каждой проблемы L в NP существует является полиномиальным сокращением многих единиц от L до H. Эквивалентное определение требует, чтобы каждая проблема L в NP могла быть решена за полиномиальное время с помощью оракула machine с оракулом для H. Неформально можно представить алгоритм, который вызывает такую машину оракула как подпрограмму для решения H и решает L за полиномиальное время, если для вычисления вызова подпрограммы требуется только один шаг.
Другое определение состоит в том, чтобы требовать, чтобы имелось полиномиальное сокращение от NP-полной задачи G до H. Поскольку любая задача L в NP сводится за полиномиальное время к G, L сводится к в свою очередь, в H за полиномиальное время, так что это новое определение подразумевает предыдущее. Как ни странно, он не ограничивает класс NP-трудных задач решениями, а также включает проблемы поиска или проблемы оптимизации.
Если P ≠ NP, то NP -сложные задачи не могут быть решены за полиномиальное время.
Некоторые NP-сложные задачи оптимизации могут быть аппроксимированы полиномиальным временем до некоторого постоянного отношения приближения (в частности, те, что в APX ) или даже до любого приближения соотношение (в PTAS или FPTAS ).
Примером NP-сложной проблемы является решение проблема суммы подмножества : при заданном наборе целых чисел складывается ли какое-либо непустое подмножество из них до нуля? Это проблема решения, которая является NP-полной. Другой пример NP-трудной задачи - задача оптимизации поиска циклического маршрута с наименьшей стоимостью через все узлы взвешенного графа. Это обычно известно как проблема коммивояжера.
. Существуют NP-трудные, но не NP-полные проблемы решения, такие как проблема остановки. Это проблема, которая спрашивает: «Будет ли она работать вечно при наличии программы и ее входных данных?» Это вопрос «да / нет», и это проблема решения. Легко доказать, что проблема остановки является NP-сложной, но не NP-полной. Например, проблема логической выполнимости может быть сведена к проблеме остановки, преобразовав ее в описание машины Тьюринга, которая пробует все значения истинности присваивания и когда он находит тот, который удовлетворяет формуле, он останавливается, а в противном случае он переходит в бесконечный цикл. Также легко увидеть, что проблема остановки не в NP, поскольку все проблемы в NP разрешимы за конечное число операций, но проблема остановки, в общем, неразрешима. Существуют также NP-сложные проблемы, которые не являются NP-полными или неразрешимыми. Например, язык истинных квантифицированных булевых формул разрешим в полиномиальном пространстве, но не в недетерминированном полиномиальном времени (если NP = PSPACE ).
NP-сложные задачи не обязательно должны быть элементами класса сложности NP. Поскольку NP играет центральную роль в вычислительной сложности, он используется в качестве основы для нескольких классов:
NP-сложные проблемы часто решаются с помощью языков, основанных на правилах, в таких областях, как:
