Pseudopolynomická časová složitost

Pseudopolynomická časová složitost je v teorii složitosti taková časová složitost, která je vzhledem k číselné hodnotě vstupu polynomická, ale fakticky se jedná vzhledem k velikosti vstupu o složitost exponenciální.

Klasickým příkladem jsou algoritmy řešící problémy z teorie čísel, například testy prvočíselnosti. Naivní implementace algoritmu zkusmého dělení se snaží zjistit, zda je zadané přirozené číslo $n$ prvočíslem, tak, že postupně zkouší dělit $n$ čísly $\{2,3,\dots ,n-1\}$. Na to potřebuje $n-2$ operací dělení, zdálo by se tedy, že se jedná o lineární závislost na vstupu. Ovšem velikostí vstupu není hodnota čísla, ale kolik zabírá místa v paměti počítače, tedy kolik má číslic. Například Mersennovu prvočíslu $2^{31}-1$ stačí k uložení v paměti počítače v obvyklém kódování jen 31 až 32 bitů, ale algoritmus zkusmého dělení by pro jeho prověření potřeboval přes dvě miliardy dělení. Obecně číslo $n$ potřebuje k uložení řádově $l={\log }_{2}n$ bitů, zkusmé dělení tedy provede zhruba $2^l$ dělení, což je závislost zjevně exponenciální.

Naproti tomu skutečně polynomickým algoritmem je například sčítání dlouhých čísel, kde školský algoritmus postupuje zprava číslici po číslici (se započítáním přenosu) a jeho časová složitost je tedy lineárně závislá nikoliv na hodnotě čísla, ale na počtu jeho číslic. Šablona:Autoritní data