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  prvočíslem, tak, že postupně zkouší dělit  čísly . Na to potřebuje  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  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  potřebuje k uložení řádově  bitů, zkusmé dělení tedy provede zhruba  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.

Teorie složitosti