Сильная NP-полнота - Strong NP-completeness

С точки зрения вычислительной сложности , сильная NP-полнота - это свойство вычислительных задач, которое является частным случаем NP-полноты . Общая вычислительная задача может иметь числовые параметры. Например, входными данными для задачи упаковки ящиков является список объектов определенных размеров и размер ячеек, которые должны содержать объекты - эти размеры объектов и размер ящика являются числовыми параметрами.

Задача называется сильно NP-полной (NP-полной в сильном смысле), если она остается NP-полной даже тогда, когда все ее числовые параметры ограничены полиномом от длины входа. Проблема называется сильно NP-трудной, если сильно NP-полная задача имеет полиномиальную редукцию к ней; в комбинаторной оптимизации, в частности, фраза «сильно NP-трудная» зарезервирована для задач, которые, как известно, не имеют полиномиального сведения к другой сильно NP-полной проблеме.

Обычно числовые параметры задачи задаются в позиционной записи , поэтому задача с размером ввода n может содержать параметры, размер которых является экспоненциальным по  n . Если мы переопределим задачу, чтобы параметры были заданы в унарной записи , тогда параметры должны быть ограничены размером ввода. Таким образом, сильная NP-полнота или NP-трудность также может быть определена как NP-полнота или NP-трудность этой унарной версии проблемы.

Например, упаковка бункера является NP-полной, а задача о ранце 0-1 - лишь частично NP-полной . Таким образом, версия упаковки контейнеров, в которой размеры объекта и ячейки являются целыми числами, ограниченными полиномом, остается NP-полной, в то время как соответствующая версия задачи о ранце может быть решена за псевдополиномиальное время с помощью динамического программирования .

С теоретической точки зрения любая сильно NP-трудная задача оптимизации с полиномиально ограниченной целевой функцией не может иметь полностью полиномиальную схему аппроксимации (или FPTAS ), если P = NP. Однако обратное неверно: например, если P не равно NP, рюкзак с двумя ограничениями не является сильно NP-трудным, но не имеет FPTAS, даже если оптимальная цель полиномиально ограничена.

Некоторые сильно NP-полные проблемы могут быть легко решаемы в среднем , но более вероятно, что на практике будут встречаться сложные случаи.

Сильная и слабая NP-трудность против сильных и слабых алгоритмов с полиномиальным временем

Предполагая, что P! = NP, для вычислительных задач с целыми числами справедливо следующее:

Рекомендации