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

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

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

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

ЛитератураПравить

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