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

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

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

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