Otazky ke zkousce z prednasky

"Slozitost pro kryptografii"

Z nasledujiciho seznamu si zkouseny vytahne (nahodne s uniformni distribuci) jednu otazku a predsvedci me, ze zna spravnou odpoved.

Otazky:

  • (1) Turingovy stroje, rekursivni funkce a castecne rek. funkce. Rekursivni mnoziny a rek. vycislitelne mnoziny. Dukaz vet:
    (i) R je prunik RE a coRE. (ii) Mnozina je RE prave kdyz je oborem hodnot PRF a tez prave kdyz je projekci rekursivni relace.

    Kodovani TM binarnimi slovy a definice universalniho TM. Formulace Halting problemu (HALT) a 10.Hilbertova problemu. Dukaz vety: HALT neni rekursivni.

  • (2) Casova slozitost TM a NTM. Polynomialni cas a trida P. Trida NP (dukaz ekvivalence definic pres NTM a jako p-omezene projekce p-relaci).
    Tridy E a EXP. NP je cast EXP (s dk.).
    P/poly: neuniformni p-cas. Charakterizace vyuzivajici pomocna slova (advice) a booleovske obvody, a dukaz jejich ekvivalence.

  • (3) p-preveditelnost, NP-uplnost. Jazyky SAT, 3SAT a CLIQUE. Cookova veta a jeji dukaz.

  • (4) Pravdepodobnostni algoritmus pro PIT (polynomial identity testing). Tridy BPP, RP, ZPP. Dukaz inkluze: BPP je cast EXP. Amplifikace pravdepodobnosti u RP a BPP. Dukaz inkluze: BPP je cast P/poly.

  • (5) Konecne pravdepodobnostni prostory, jevy, nahodne veliciny. Ocekavana (stredni) hodnota E(X). Linearnost E(X).
    Podminena pravdepodobnost, nezavisle jevy a nahodne veliciny. Markovova nerovnost (dukaz) a Chernoffova (bez dk.). Distribuce.

  • (6) Vypocetne nerozlisitelne distribuce, zakladni vlastnosti. Pseudonahodne distribuce a pseudonahodne generatory (PRNG) a souvislost s P vs. NP problemem.
    Vlastnosti PRNG a dusledky jejich existence: polynomialni prodlouzeni (dukaz), derandomizace BPP do sub-exp.casu a pseudonahodne funkce (bez dk.).

  • (7) Jednosmerne funkce (OWF). Priklady predpokladanych OWF.: rozklad na prvocisla, diskretni logaritmus, RSA, Rabinova funkce.
    Veta: Existence OWF implikuje existenci PRNG (bez dk.). Dukaz slabsi verse: Existence OWP (permutace) implikuje existenci PRNG. Tezky bit OWF. Goldreich-Levinuv algoritmus a veta (s dukazem).

  • (8) Interaktivni dukazove systemy. Trida IP. Dukazy pozorovani: NP a RP jsou casti IP. Shamirova veta: IP=PSPACE (bez dukazu). Dukaz specialniho pripadu: coNP je cast IP.

  • (9) PCP dukazovy system. PCP veta (bez dukazu). Alternativni formulace: amplifikace minimalniho poctu nesplnenych klausuli v 3CNF formulich. Dukaz ekvivalence obou formulaci. Idea aplikace: ne-aproximovatelnost optimalizacnich NP-uplnych uloh.

  • (10) Definice Zero-knowledge (dukazove systemy s nulovou znalosti). Varianty: perfektni (PZK), statisticka (SZK) a vypocetni (CZK). PZK protokoly pro grafovy izomorfismus a neizomorfismus. CZK protokol pro vsechny NP mnoziny (za predpokladu existence OWF): idea konstrukce CZK protokolu pro 3COLOR.