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 ${\displaystyle n}$ prvočíslem, tak, že postupně zkouší dělit ${\displaystyle n}$ čísly ${\displaystyle \left\{2,3,\dots ,n-1\right\}}$. Na to potřebuje ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n}$ potřebuje k uložení řádově ${\displaystyle l=\log _{2}n}$ bitů, zkusmé dělení tedy provede zhruba ${\displaystyle 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.