Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a~rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostné složitostní třídy a jejich struktura.
• Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.