Сильная NP-полнота
В сложности вычислительной сильная NP-полнота — это свойство вычислительных задач, которое является частным случаем NP-полноты . Общая вычислительная задача может иметь числовые параметры. Например, входными данными для задачи упаковки контейнеров является список объектов определенных размеров и размер контейнеров, которые должны содержать объекты — эти размеры объектов и размер контейнера являются числовыми параметрами.
Задача называется сильно NP-полной (NP-полной в сильном смысле), если она остается NP-полной, даже когда все ее числовые параметры ограничены полиномом от длины входных данных. [1] Задача называется сильно NP-трудной , если сильно NP-полная задача имеет к ней полиномиальную редукцию; в частности, в комбинаторной оптимизации фраза «строго NP-трудная» зарезервирована для задач, которые, как известно, не имеют полиномиальной редукции к другой сильно NP-полной задаче.
Обычно числовые параметры задачи задаются в позиционной записи , поэтому задача входного размера n может содержать параметры, размер которых является экспоненциальным по n . Если мы переопределим задачу, чтобы параметры были заданы в унарной записи , тогда параметры должны быть ограничены входным размером. Таким образом, сильную NP-полноту или NP-трудность можно также определить как NP-полноту или NP-трудность этой унарной версии задачи.
Например, упаковка контейнеров является строго NP-полной, тогда как задача о рюкзаке 0-1 лишь слабо NP-полна . Таким образом, версия упаковки контейнеров, в которой размеры объекта и контейнера являются целыми числами, ограниченными полиномом, остается NP-полной, в то время как соответствующая версия задачи о рюкзаке может быть решена за псевдополиномиальное время с помощью динамического программирования .
С теоретической точки зрения любая сильно NP-трудная задача оптимизации с полиномиально ограниченной целевой функцией не может иметь полностью полиномиальную схему аппроксимации (или FPTAS ), если только P = NP. [2] [3] Однако обратное неверно: например, если P не равно NP, рюкзак с двумя ограничениями не является строго NP-сложным, но не имеет FPTAS, даже если оптимальная цель полиномиально ограничена. [4]
все еще могут быть легко решены Некоторые сильно NP-полные задачи в среднем , но более вероятно, что на практике будут встречаться трудные случаи.
Сильная и слабая NP-трудность в сравнении с сильными и слабыми алгоритмами с полиномиальным временем
[ редактировать ]Предполагая P ≠ NP, для вычислительных задач с целыми числами справедливы следующие условия: [5]
- Если задача является слабо NP-трудной , то она не имеет алгоритма со слабо полиномиальным временем (полиномиальным по числу целых чисел и количеству бит в наибольшем целом), но может иметь алгоритм псевдополиномиального времени (полиномиальный по числу целых чисел и величину наибольшего целого числа). Примером является проблема с разделами . И слабая NP-трудность, и слабое полиномиальное время соответствуют кодированию входных агентов в двоичном кодировании .
- Если задача сильно NP-трудна , то для нее даже не существует алгоритма с псевдополиномиальным временем . Он также не имеет полностью полиномиальной схемы аппроксимации по времени . Примером может служить проблема с тремя разделами . И сильная NP-жесткость, и псевдополиномиальное время соответствуют кодированию входных агентов в унарном кодировании .
Ссылки
[ редактировать ]- ^ Гэри, MR ; Джонсон, DS (июль 1978 г.). « Сильные» результаты NP-полноты: мотивация, примеры и последствия» . Журнал Ассоциации вычислительной техники . 25 (3). Нью-Йорк, штат Нью-Йорк: ACM: 499–508. дои : 10.1145/322077.322090 . ISSN 0004-5411 . МР 0478747 . S2CID 18371269 .
- ^ Vazirani, Vijay V. (2003). Approximation Algorithms . Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8 . МР 1851303 .
- ^ Гэри, MR ; Джонсон, Д.С. (1979). Виктор Клее (ред.). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам. Сан-Франциско, Калифорния: WH Freeman and Co., стр. x+338 . ISBN 0-7167-1045-5 . МР 0519066 .
- ^ Х. Келлерер; У. Пферши; Д. Пизингер (2004). Проблемы с рюкзаком . Спрингер.
- ^ Демейн, Эрик. «Алгоритмические нижние границы: развлечения с доказательствами твердости, лекция 2» .