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.

Uvedený seznam je orientační, konkrétní náplň přednášek je přispůsobena znalostem a zájmům posluchačů.