С точки зрения вычислительной сложности , сильная 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-полные проблемы могут быть легко решаемы в среднем , но более вероятно, что на практике будут встречаться сложные случаи.
См. Также [ править ]
Ссылки [ править ]
- ^ Garey, MR ; Джонсон, Д.С. (июль 1978 г.). « „ Сильная“NP-полнота Результаты: Мотивация, примеры и последствие». Журнал Ассоциации вычислительной техники . Нью-Йорк, штат Нью-Йорк: ACM. 25 (3): 499–508. DOI : 10.1145 / 322077.322090 . ISSN 0004-5411 . Руководство по ремонту 0478747 .
- ^ Вазирани, Виджай В. (2003). Аппроксимационные алгоритмы . Берлин: Springer. С. 294–295. ISBN 3-540-65367-8. Руководство по ремонту 1851303 .
- ^ Гарей, М. Р .; Джонсон, Д. С. (1979). Виктор Клее (ред.). Компьютеры и непоколебимость: руководство по теории NP-полноты . Серия книг по математическим наукам. Сан-Франциско, Калифорния: W. H. Freeman and Co., стр. X + 338 . ISBN 0-7167-1045-5. Руководство по ремонту 0519066 .
- ^ H. Kellerer и У. Pferschy и Д. Pisinger (2004). Проблемы с рюкзаком . Springer.CS1 maint: использует параметр авторов ( ссылка )
