Наряду с разделением задач на NP-трудные и полиномиально разрешимые, NP-трудные задачи, в свою очередь, подразделяются на NP-трудные в сильном смысле задачи и задачи, имеющие псевдополиномиальные алгоритмы решения.
Алгоритм решения задачи Π называется псевдополиномиальным, если его временная сложность не превосходит некоторого полинома от двух переменных Lengthn[I] и Maxц[I] для любого примера I задачи Π. Соответствующая задача называется псевдополиномиалъно разрешимой.
Нетрудно заметить, что любой полиномиальный алгоритм является одновременно и псевдополиномиальным. Кроме того, ни одна из NP-трудных задач, не имеющая числовых параметров, не может иметь псевдополиномиального алгоритма решения, если
В противном случае такая задача имела бы полиномиальный алгоритм решения, поскольку для любого ее примера. Аналогично, если для задачи Π существует такой полином, что для любого то Π, удучи NP-трудной, не может быть псевдополиномиально разрешимой.
Таким образом, существуют NP-трудные задачи, которые не могут иметь даже псевдополиномиальных алгоритмов решения. Такие задачи образуют множество так называемых NP-трудных в сильном смысле задач. Для формализации понятия NP-трудной в сильном смысле задачи введем определение псевдополиномиальной сво димости задач распознавания.
|
|
Пусть пары функций (Lengthn, Maxц) и (Lengthu', Maxц>) сопоставлены задачам Π и Π' соответственно.
Говорят, что задача распознавания Π псевдополиномиалъно сводится к задаче распознавания Π', если существует словарная функция Φ, переводящая задачу Π в задачу Π' и удовлетворяющая следующим условиям:
(а) для любого примера соотношение выполняется тогда и только тогда, когда выполняется
(б) временная сложность вычисления функции Φ не превосходит некоторого полинома q от двух переменных Lengthn[I] и Maxп [I ];
(в) существуют такие полиномы q i и qi, что для любого I
Задача распознавания Π называется NP-трудной в сильном смысле, если существует NP-трудная задача распознавания Π, которая псевдополиномиально сводится к Π и для любого
Поскольку любая задача псевдополиномиально сводится к себе, то любая NP-трудная задача, удовлетворяющая условию (1.3), является NP-трудной в сильном смысле. Кроме того, любая NP-трудная в сильном смысле задача является NP-трудной, и ни одна из NP-трудных в сильном смысле задач не может иметь псевдополиномиального алгоритма решения, если
Понятие псевдполиномиальной сводимости транзитивно. Поэтому для доказательства NP-трудности в сильном смысле некоторой задачи достаточно псевдополиномиально свести к ней некоторую NP-трудную задачу.
|
|
Задача распознавания Π называется NP-полной в сильном смысле, если Π и Π является NP-трудной в сильном смысле.
Экстремальная комбинаторная задача называется NP-трудной в сильном смысле, если сопоставленная ей задача распознавания NP-трудна в сильном смысле.
Примеры NP-трудных задач
Ниже приведены формулировки NP-трудных задач, которые в дальнейшем используются при доказательстве NP-трудности задач оптимального планирования.
Разбиение:
Заданы целые положительные числа aл, aо,..., aг и A такие,
Требуется определить, существует ли множество такое что