Участник:CLepip/NP-hardness
Материал из Википедии — свободной encyclopedia
В теории сложности вычислений NP-трудность (недетерминированная полиномиальная трудность по времени) является определяющим свойством класса задач, которые неформально «по крайней мере так же сложны, как самые сложные задачи в NP». Простым примером NP-трудной задачи является задача о сумме подмножеств.
Формальное определение: задача разрешимости является NP-трудной, когда любая задача из NP может быть сведена за полиномиальное время к . Эквивалентно условие требует, чтобы каждая задача в NP могла быть решена за полиномиальное время с оракулом для [1][2]. Как следствие, алгоритм с полиномиальным временем для решения любой NP-сложной задачи даст алгоритмы с полиномиальным временем для всех задач в NP.
Считается что алгоритмов с полиномиальным временем для NP-сложных задач не существует, но это не доказано (см. проблему P≠NP).[3][4] Более того, класс P, в котором все задачи решаются за полиномиальное время, содержится в классе NP[5].
Некоторые NP-сложные задачи оптимизации могут быть полиномиально аппроксимированы до некоторого постоянного (константного) коэффициента аппроксимации (в частности, в APX) или даже до любого коэффициента аппроксимации (в PTAS или FPTAS).