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í
   • Výsledky o neaproximovatelnosti
4. PSPACE
   • zavedení PSPACE-úplnosti
   • problém KBF
   • hra na grafech
5. Booleovská složitost
   • DNF, KNF, rozhodovací stromy
   • odhady složitosti konkrétních funkcí
   • porovnání výpočetní síly uvedených modelů
6. 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