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