Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost, konkrétně

• Algoritmus a jeho výpočetní model. Churchova teze.
• Deterministické a nedeterministické Turingove stroje.
• Výpočetní složitost problémů.
• Složitostní třídy.
• Redukce a polynomiální redukce, těžké a úplné problémy.