Otazky ke zkousce z prednasky "Slozitost pro kryptografii"

Kazdy si vylosuje jednu z hlavnich otazek (1) - (6). V pripade nejasnosti ohledne znamky dostane jeste jednu z pomocnych otazek (a) - (c).

Hlavni otazky:

  • (1) p-preveditelnost, NP-uplnost. Jazyky SAT, 3SAT, CIRCSAT, EXACT3SAT a CLIQUE. Simulace vypoctu T.stroju obvody. Cookova veta a jeji dukaz. Dukaz NP-uplnosti CLIQUE.

  • (2) 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 (dukaz) a pseudonahodne funkce (bez dk.).

  • (3) 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).

  • (4) 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.

  • (5) PCP dukazovy system. PCP veta (bez dukazu). Alternativni formulace: amplifikace minimalniho poctu nesplnenych klausuli v 3CNF formulich. Dukaz ekvivalence obou formulaci. Aplikace: ne-aproximovatelnost MAX-3SAT (s dk.).

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

    Pomocne otazky:

  • (a) 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.

  • (b) 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.

  • (c) Konecne pravdepodobnostni prostory, jevy, nahodne veliciny. Ocekavana (stredni) hodnota E(X). Linearnost E(X) Podminena pravdepodobnost, nezavisle jevy a nezavisle nahodne veliciny. Markovova nerovnost (dukaz) a Chernoffova (bez dk.). Distribuce.
    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.