В теории сложности класс сложности NP-easy — это множество функциональных задач , которые решаются за полиномиальное время с помощью детерминированной машины Тьюринга с оракулом для некоторой задачи принятия решений из NP .
Другими словами, задача X является NP-легкой тогда и только тогда, когда существует некоторая задача Y из NP, такая, что X сводима по Тьюрингу к Y за полиномиальное время. [1] Это означает, что при наличии оракула для Y существует алгоритм, который решает X за полиномиальное время (возможно, путем многократного использования этого оракула).
NP-easy — это другое название для FP NP (см. статью о задачах на функции ) или для FΔ 2 P (см. статью о иерархии полиномов ).
Примером NP-легкой задачи является задача сортировки списка строк. Задача принятия решения «больше ли строка A, чем строка B» относится к NP. Существуют алгоритмы, такие как быстрая сортировка , которые могут сортировать список, используя только полиномиальное число вызовов процедуры сравнения, плюс полиномиальное количество дополнительной работы. Поэтому сортировка относится к NP-легким задачам.
Существуют также более сложные задачи, которые являются NP-легкими. См. NP-эквивалент для примера.
Определение NP-easy использует редукцию Тьюринга, а не редукцию многих-единиц , поскольку ответы на задачу Y могут быть только ИСТИНА или ЛОЖЬ, но ответы на задачу X могут быть более общими. Следовательно, не существует общего способа перевести экземпляр X в экземпляр Y с тем же ответом.