Введение
В теории вычислительной сложности, класс сложности NP-эквивалент представляет собой набор функциональных задач, которые одновременно NP-легки и NP-трудны. NP-эквивалент является аналогом NP-полноты для функциональных задач. Например, задача FIND SUBSET SUM (НАЙТИ СУММУ ПОДМНОЖЕСТВА) является NP-эквивалентной. Для заданного набора целых чисел, FIND SUBSET SUM – это задача поиска непустого подмножества, сумма элементов которого равна нулю (или возврата пустого множества, если такого подмножества не существует). Эта задача оптимизации аналогична задаче принятия решений SUBSET SUM (СУММА ПОДМНОЖЕСТВА). Для заданного набора целых чисел, SUBSET SUM – это задача определения, существует ли подмножество, сумма элементов которого равна нулю. SUBSET SUM является NP-полной. Чтобы показать, что FIND SUBSET SUM является NP-эквивалентной, необходимо доказать, что она одновременно NP-трудная и NP-легкая. Очевидно, что она NP-трудная. Если бы у нас был "черный ящик", решающий FIND SUBSET SUM за единицу времени, то решить SUBSET SUM было бы легко. Достаточно запросить "черный ящик" найти подмножество с нулевой суммой, а затем проверить, вернул ли он непустое множество. Она также NP-легкая. Если бы у нас был "черный ящик", решающий SUBSET SUM за единицу времени, мы могли бы использовать его для решения FIND SUBSET SUM. Если он возвращает false, мы немедленно возвращаем пустое множество. В противном случае мы последовательно просматриваем каждый элемент и удаляем его, если SUBSET SUM по-прежнему возвращает true после удаления. После просмотра всех элементов мы больше не сможем удалить ни один элемент, не изменив ответ с true на false; в этот момент оставшееся подмножество исходных элементов должно суммироваться к нулю. Важно отметить, что последующее удаление элементов не изменяет тот факт, что удаление предыдущего элемента изменило ответ с true на false. В псевдокоде:
function FIND SUBSET SUM(set S)
if not(SUBSET SUM(S))
return {}
for each x in S
if SUBSET SUM(S – {x})
S := S – {x}
return S
if not(SUBSET SUM(S))
return {}
for each x in S
if SUBSET SUM(S – {x})
S := S – {x}
return S
Другая хорошо известная NP-эквивалентная задача – задача коммивояжера.
Уточнение
В этом контексте NP обозначает недетерминированное полиномиальное время. Существуют также классы эквивалентности булевых функций, для которых NP обозначает отрицание и перестановку.