Anotace
Přednáška seznamuje s matematickými prostředky pro studium náročnosti řešení úloh na počítači z hlediska délky výpočtu a množství potřebné paměti. Jsou vysvětleny základní prostředky pro zařazení úloh do tříd P, NP a PSPACE a jsou studovány některé obecné vlastnosti tříd složitosti.
Kromě toho se přednáška zabývá jednoduchými modely Booleovské složitosti a některými aplikacemi teorie čísel na kryptografii.