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).