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

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

Більш точне визначення виглядає так. Нехай M(z) — деяка функція, що задає значення числового параметра індивідуальної задачі z. Якщо таких параметрів декілька, як M(z) можна взяти або максимальне, або середнє значення, а якщо задача зовсім не має числових параметрів (наприклад, розфарбування графу, шахи тощо), то M(z) = 0. Алгоритм називається псевдополіноміальним, якщо він має оцінку складності t_макс(z) = O(P(| z |, M (z))), де P — деякий поліном від двох змінних.

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