2.6. Псевдополиномиальные задачи

Приведенный список NP-полных задач включает и рассмотренную нами ранее задачу о рюкзаке. Однако в п.1.7 была приведена оценка эффективности алгоритма Беллмана для этой задачи: T(n,B) = O(nB²). Это ведь полиномиальная оценка, причем очень невысокой степени. Практика также подтверждает высокую эффективность данного алгоритма. Так что же, не тот ли это самый случай полиномиального алгоритма для NP-полной задачи, из которого должно проистечь столько хороших последствий?

Не все так просто.

В п.2.1 уже отмечалось, что в качестве аргумента оценок эффективности следует использовать не расплывчатое понятие «размерность задачи», а четко определенное «длина описания задачи». Однако как связан параметр объема рюкзака B с длиной соответствующей задачи |z|? Поскольку B – целое число, а длина любой разумной кодировки числа пропорциональна логарифму этого числа, то при фиксированном n имеем: |z| = O(log(B)), откуда получаем: B = O(2^|z|). Значит, полиномиальная относительно B оценка эффективности алгоритма Беллмана является на самом деле экспоненциальной относительно |z|. Но если алгоритм экспоненциальный, то почему он столь эффективен? Дело в том, что существенное замедление работы алгоритма будет ощущаться только при очень больших значениях B. Заметим, что увеличение длины описания задачи на каких-то 20 битов позволяет задать в 1000000 раз большее значение B! Конечно, такая задача будет за пределами практической разрешимости.

Подобная ситуация, когда для задачи, имеющей числовые¹ параметры, известен алгоритм, проявляющий экспоненциальный характер только при очень больших значениях параметров, встречается не так уж редко. Подобные алгоритмы, как и решаемые ими задачи, носят название псевдополиномиальных.

Более строгое определение выглядит так. Пусть M(z) – некоторая функция, задающая значение числового параметра индивидуальной задачи z. Если таких параметров несколько, в качестве M(z) можно взять или максимальное, или среднее значение, а если задача вовсе не имеет числовых параметров (например, раскраска графа, шахматы и т.п.), то M(z) = 0. Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкости Tмакс(z) = O(P(|z|, M(z))), где P – некоторый полином от двух переменных.

Ясно, что всякий полиномиальный алгоритм является также и псевдополиномиальным (с полиномом, не зависящим от второго аргумента), обратное же, как мы видели, не имеет места.

Псевдополиномиальные алгоритмы, формально относящиеся к экспоненциальным, на практике работают как полиномиальные во всех случаях, кроме очень больших значений числового параметра.

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

Существуют NP-полные задачи с числовыми параметрами, для которых нет и не может быть псевдополиномиальных алгоритмов². Такие задачи называются NP-полными в сильном смысле. К их числу относятся, например, задача о коммивояжере и задача о трех станках.