Псевдополиномиальное сведение задач и NP-трудные в сильном смысле задачи

Наряду с разделением задач на 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-трудной в сильном смысле.