NP

Definice: pokud libovolný problém A leží ve třídě NP a každý problém z NP je na něj polynomiálně převoditelný, říkáme, že A je NP úplný

Věta: (cookova-Levinova) SAT je NP-úplný problém.

Další NP-úplný problémy:

• Hamiltnovksá kružnice - cyklus kružnice, který prochází všemi vrcholy grafu

• Součet podmnožin

  • př.: M= {1,3,10,11,20}

Součet	13	2	22	16
Ex.	ano	ne	ano	ne