1. NP-těžké problémy jako problémy rozlišující P a NP
2. Polynomiální redukce jako nástroj pro určování těžkosti problémů

Cvičení:

• časová složitost algoritmů
• vztah P a NP
• důkaz NP-těžkosti problému pomocí redukce z 3SAT