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