Псевдополиномиальный алгоритм

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

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

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

Литература

• Дроздов С.Н. Комбинаторные задачи и элементы теории вычислительной сложности: Учебное пособие. — Таганрог: Изд-во ТРТУ, 2000. — С. 58.

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.