1. Polynomiální redukce
2. NP těžké problémy
3. Rozdíl mezi nalezením a ověřením řešení, třída NP
4. Vztah tříd P a NP

Literatura: 
J. Hromkovič kapitola 5

 

Cvičení:

• příklady NP těžkých problémů
• (polynomiální) redukce