# Zkouška

verze 2025/2026; k tvrzením, jež jsme dokazovali na přednášce, bude požadován důkaz

## Skupina A

- Riceova věta, důkaz pomocí $m$-převoditelnosti.
- Savičova věta.
- Deterministická prostorová hierarchie.
- Deterministická časová hierarchie.
- Cookova-Levinova věta (NP-úplnost SAT)

## Skupina B

- Univerzální Turingův stroj a nerozhodnutelnost jazyka univerzálního Turingova stroje.
- RAM a ekvivalence s Turingovým strojem.
- Vlastnosti (turingovsky) rozhodnutelných a částečně rozhodnutelných jazyků (uzávěrové vlastnosti, Postova věta, enumerátory).
- Definice základních tříd složitosti a důkaz $\text{NTIME}(f(n))\subseteq\text{SPACE}(f(n))$ .
- Definice základních tříd složitosti a důkaz věty o vztahu prostoru a času (…).
- Dvě definice třídy NP a jejich ekvivalence.
- Polynomiální převod 3-SAT na Vrcholové pokrytí.
- Definice třídy FPT a kernelu a jejich souvislost. Kernelizace Vrcholového pokrytí
- Definice třídy FPT a parametrizovaný algoritmus pro Vrcholové pokrytí založený na prohledávání s omezenou hloubkou (se složitostí menší než $O^*(2^k)$).
- Třída \#P a \#P-úplnost, důkaz těžkosti počítání cyklů v grafu.
- Třída co-NP a co-NP-úplnost.
- Pseudonáhodné generátory, jednosměrné funkce a jejich souvislost s kryptografií (symetrické šifrování, bit-commitment).
- Příklad zjemnělé redukce (redukce SETH na OV nebo OV na hledání regulárního výrazu v textu).