NP-трудность

---

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

Формальное определение: задача разрешимости ${\displaystyle H}$ является NP-трудной, если любая задача ${\displaystyle L}$ из NP может быть сведена за полиномиальное время к ${\displaystyle H}$. Эквивалентно условие требует, чтобы каждая задача ${\displaystyle L}$ в NP могла быть решена за полиномиальное время с оракулом для ${\displaystyle H}$^[1][2]. Как следствие, алгоритм с полиномиальным временем для решения любой NP-трудной задачи даст алгоритмы с полиномиальным временем для всех задач в NP.

Считается что алгоритмов с полиномиальным временем для NP-трудных задач не существует, но это не доказано (см. проблему P≠NP)^[3]. Более того, класс P, в котором все задачи решаются за полиномиальное время, содержится в классе NP^[4].

Некоторые NP-трудные задачи оптимизации могут быть полиномиально аппроксимированы до некоторого постоянного (константного) коэффициента аппроксимации (в частности, в APX) или даже до любого коэффициента аппроксимации (в PTAS или FPTAS).

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

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

---