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

Cvičení

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

Literatura:
J. Hromkovič kapitola 5