Otázky ke státní zkoušce z výpočtové složitosti

1. Základní pojmy výpočtové složitosti
   • formalizace pojmu úloha
   • výpočetní modely (varianty TS, RAM, Booleovské obvody)
   • měření složitosti
   • vztah rozhodovacích a obecných úloh
   • polynomiální ekvivalence výpočetních modelů
2. NP-úplnost
   • třída NP
   • p-převoditelnost a její vlastnosti
   • NP-úplné úlohy
   • SAT je NP-úplný
   • další NP-úplné úlohy
3. Efektivní algoritmy pro varianty NP-úplných úloh
   • problém batohu při jednotkovém kódování vstupu
   • 2-SAT
   • aproximační algoritmus pro
     • problém obchodního cestujícího
     • problém vrcholového pokrytí
     • problém množinového pokrytí
     • problém maximálního řezu
4. Obecné složitostní třídy
   • Blumova teorie složitosti
   • věta o dírách
   • věta o zrychlení
   • konstruovatelné funkce
   • věty a časové a prostorové hierarchii
5. PSPACE
   • zavedení PSPACE-úplnosti
   • problém KBF
   • hra na grafech
6. Booleovská složitost
   • DNF, KNF, rozhodovací stromy
   • odhady složitosti konkrétních funkcí
   • porovnání výpočetní síly uvedených modelů
7. Kryptografické systémy s veřejným klíčem
   • zákadní věty z teorie čísel
   • testy prvočíselnosti
   • RSA
   • Diffie-Hellmanův systém distribuce utajeného náhodného klíče