Úloha 1 (Polynomy): Nahlédněte, že množina všech polynomů je nejmenší množina funkcí z $\R$ do $\R$, která obsahuje všechny konstantní funkce, identitu a je uzavřená na sčítání, násobení a skládání funkcí. Pokud tedy prohlásíme za efektivní právě polynomiální algoritmy, platí, že složením efektivních algoritmů (v mnoha možných smyslech) je zase efektivní algoritmus. To je velice příjemná vlastnost.

Úloha 2 (3D párování): Převeďte 3D-párování na SAT.

Úloha 3 (Nerozhodování): Co jsme ztratili omezením na rozhodovací problémy? Dokažte pro libovolný problém z přednášky, že pokud bychom ho dokázali v polynomiálním čase vyřešit, uměli bychom polynomiálně řešit i „zjišťovací“ verzi (najít konkrétní párování, splňující ohodnocení, kliku apod.).

Úloha 4 (Převodoekvivalence): Ukažte vzájemné převody mezi následujícími problémy ($k$ není nutně stejné):

• Existuje nezávislá množina velikosti $k$?
• Existuje klika velikosti $k$?
• Existuje vrcholové pokrytí velikosti nejvýše $k$?

Úloha 5 (DNF): Vyřešte SAT pro formule v DNF (klauzule jsou spojené $\vee$, literály v klauzuli $\wedge$) v polynomiálním čase.