Войти
В теории вычислительной сложности, класс сложности NP-эквивалент - это набор функциональных задач, которые одновременно являются NP-easy и NP-hard. NP-эквивалент является аналогом NP-complete для функциональных задач.
. Например, задача 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 после того, как мы удалим его. После посещения каждого элемента мы больше не сможем удалить какой-либо элемент, не изменив ответ с истины на ложь; в этот момент сумма оставшегося подмножества исходных элементов должна быть равна нулю. Это требует, чтобы мы заметили, что последующее удаление элементов не меняет того факта, что удаление более раннего элемента изменило ответ с истинного на ложный. В псевдокоде:
функция FIND-SUBSET-SUM (set S) ifnot (SUBSET-SUM (S)) возвращает {} для каждого x inS ifSUBSET-SUM (S - {x}) S: = S - {x} return SДругая хорошо известная проблема NP-эквивалента - это задача коммивояжера.
