Zkouška 22.1. Hubička

1. Definujte P, NP třídu problémů, definujte NP-úplné problémy, napište Cookovu větu(bez důkazu), příklad a důkaz NP-úplného problému (s využitím Cookovy věty).

2. Sestavte hradlovou síť, která pro 2 n-bitová čísla rozhodne, které je větší.

3. Permanent matice se počítá jako determinant matice, ale všechny jeho členy jsou kladné. Jak zjistit, jestli pro zadanou nula jedničkovou matici je permanent rovný nule.

Řešení dvojky už tu myslím někde je, tak aspoň něco k trojce.

Byl to úkol na nalezení dokonalého párování. Stačí si uvědomit ze je nutné najít jedinou permutaci pozic prvků, kde ani na jedné nebude nula.
Tedy jedna partita budou řádky matice, druhá sloupce, a každý řádek napojíme na ty sloupce, kde jsou v něm nenulové hodnoty. Pak už stačí v tomto grafu najít párování, pokud existuje tak je permanent nenulový.