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.