NP-эквивалент

В теории сложности вычислений класс сложности NP-эквивалент представляет собой набор функциональных задач , которые являются одновременно NP-простыми и NP-сложными . ^[1] NP-эквивалент является аналогом NP-полной для функциональных задач .

Например, задача FIND-SUBSET-SUM находится в NP-эквиваленте. Учитывая набор целых чисел , FIND-SUBSET-SUM — это проблема поиска некоторого непустого подмножества целых чисел, сумма которых равна нулю (или возврата пустого набора, если такого подмножества нет). Эта проблема оптимизации аналогична проблеме принятия решения SUBSET-SUM . Учитывая набор целых чисел, SUBSET-SUM — это проблема определения, существует ли подмножество, суммирующееся до нуля. SUBSET-SUM является NP-полным.

Чтобы показать, что FIND-SUBSET-SUM NP-эквивалентен, мы должны показать, что он одновременно NP-сложный и NP-легкий.

Очевидно, что это NP-трудно. Если бы у нас был черный ящик , который решал НАЙТИ-ПОДНАБОР-СУММ за единицу времени, то решить ПОДМНОЖЕ-СУММ было бы легко. Просто попросите черный ящик найти подмножество, сумма которого равна нулю, а затем проверьте, вернул ли он непустое множество.

Это также NP-просто. Если бы у нас был черный ящик, который решал ПОДНАБОР-СУММ за единицу времени, мы могли бы использовать его для решения НАЙТИ-ПОДНАБОР-СУММ. Если он возвращает 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

Другая известная NP-эквивалентная задача — задача коммивояжера .

Разъяснение

В этом контексте NP означает недетерминированное полиномиальное время .
Существуют также классы NP-эквивалентности булевых функций , где NP означает отрицание и перестановку . ^[2]

Примечания

^ Гари и Джонсон (1979) , с. 117, 120.
^ См., например, последовательность A000616 в OEIS . Часто используется в контексте классов NPN-эквивалентности. (Например, в новом попарном алгоритме логического сопоставления NPN.... )

Ссылки

Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 . .

[1] Гари и Джонсон (1979) , с. 117, 120.

[2] См., например, последовательность A000616 в OEIS . Часто используется в контексте классов NPN-эквивалентности. (Например, в новом попарном алгоритме логического сопоставления NPN.... )

[1]

[2]