Pseudopolynomiální algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. září 2015; kontroly vyžadují 5 úprav .

Pseudopolynomiální algoritmus - v teorii výpočetní složitosti se jedná o polynomiální algoritmus, který vykazuje exponenciální charakter pouze pro velmi velké hodnoty číselných parametrů.

Přesnější definice vypadá takto. Dovolit být nějaká funkce, která specifikuje hodnotu číselného parametru jednotlivého problému . Je-li takových parametrů více, lze za hodnotu vzít buď maximální nebo průměrnou hodnotu, a pokud problém nemá vůbec žádné číselné parametry (například zbarvení grafu, šachy atd.), pak . Algoritmus se nazývá pseudopolynom, pokud má odhad nákladů , kde je nějaký polynom ve dvou proměnných.

Polynomiální algoritmus je také pseudopolynomiální (s polynomem nezávislým na druhém argumentu), ale obráceně tomu tak není. Pseudopolynomiální algoritmy, formálně příbuzné exponenciálním algoritmům, v praxi fungují jako polynomy ve všech případech, s výjimkou velmi velkých hodnot číselného parametru.

Literatura