Sylabus a literatura k prednasce
"Slozitost pro kryptografii",
Jan Krajicek
Kod predmetu: NMIB002
Zkouska je ustni
(otazky).
Alternativa
pro studenty, kteri prednasku uspesne absolvovali v ramci
bakalarskeho studia a maji ji zapsanou podruhe v ramci
magisterskeho studia.
Sylabus:
Bijekce mezi slovy nad konecnou abecedou a prirozenymi
cisly. Jazyky a rozhodovaci problemy.
Turingovy stroje (TM). Varianty TM (vice pasek, atd.).
Rekursivni funkce (RF) a castecne rek. fce (PRF).
Rekursivni mnoziny (R=Delta_1) a rek. vycislitelne
mnoziny (RE = Sigma_1). coRE (= Pi_1) mnoziny.
Vety: R je prunik RE
a coRE. Mnozina je RE prave kdyz
je oborem hodnot PRF a tez prave kdyz je projekci rekursivni relace.
Souvislost RE mnozin a NTM (nedeterministicke TM).
Kodovani TM slovy. Universalni TM. Halting problem (HALT)
a 10.Hilbertuv problem. HALT neni rekursivni.
Casova slozitost TM a NTM. Polynomialni cas (p-cas), trida P.
Trida NP (ekvivalence definic pres NTM a jako
p-omezene projekce p-relaci).
Prostorova slozitost, tridy L, NL a PSPACE. Obecne vztahy
mezi casovou a prostorovou slozitosti:
TIME(f) je cast NTIME(f) je cast SPACE(f)
je cast TIME(2^{O(f)}).
s-t souvislost v orientovanych grafech (algoritmus s
log^2(n) prostorovou slozitosti).
Savitchova veta: NSPACE(f) je cast SPACE(O(f^2)).
Immerman - Szelepscenyi veta: NSPACE(f) =
coNSPACE(f) (bez dk.).
Hierrarchie trid slozitosti:
SPACE(f) je vlastni cast SPACE(g) (je-li f = o(g)),
TIME(f) je vlastni cast TIME(g) (je-li f log(f) = o(g)) (bez dk.).
Tridy E a EXP. NP je cast EXP.
Vyrokova logika, booleovske obvody.
p-preveditelnost. NP-uplne jazyky. Cook-Levinova veta.
SAT, CIRCSAT, 3SAT, 3-obarvitelnost.
Clanky
Cook'71 a
Karp'72.
P/poly: neuniformni p-cas. Charakterizace vyuzivajici pomocna
slova (advice) a booleovske obvody, a jejich ekvivalence.
Pozn. o spodnich odhadech pro obvody a souvislosti s P/NP
problemem.
Pravdepodobnostni algoritmy. Priklady: PIT (polynomial identity
testing) a nahodne prochazky po grafech (s-t souvislost; toto bez dk.).
Tridy BPP, RP, ZPP. BPP je cast EXP. Amplifikace pravdepodobnosti
u RP.
Pozn. o hypoteze P = BPP (Impagliazzo-Wigdersonova veta - bez dk.).
Konecne pravdepodobnostni prostory, jevy, nahodne veliciny.
Ocekavana (stredni) hodnota E(X). Linearnost E(X).
Pr.: pocet hlav v n hodech minci.
Podminena pravdepodobnost, nezavisle jevy a nahodne veliciny,
odchylka. Po dvou nezavisle veliciny a linearnost Var(X).
Markovova nerovnost, Cebysevova nerovnost (obe s dk.)
a Chernoffova (bez dk.).
Amplifikace pravdepodobnosti u BPP. BPP je v P/poly.
Distribuce a jejich konstruovatelnost. Zanedbatelne a vyznamne funkce.
Vypocetne nerozlisitelne distribuce, zakladni vlastnosti.
Poly-mnoho nezavislych kopii.
Pseudonahodne distribuce. Pseudonahodne generatory (PRNG) a souvislost
s P vs. NP problemem.
Vlastnosti PRNG a dusledky jejich existence: polynomialni prodlouzeni,
derandomizace BPP do sub-exp.casu a pseudonahodne funkce (bez dk.).
Jednosmerne funkce (OWF). Slabe OWF a ekvivalence s puvodni
definici (bez dk.). PRNG s dostatecnym prodlouzenim
je OWF. Pr.: rozklad na prvocisla,
diskretni logaritmus, RSA, Rabinova funkce, subset-sum generator.
Veta: Existence OWF implikuje existenci PRNG (bez dk.). Dukaz slabsi verse:
Existence OWP (permutace) implikuje existenci PRNG.
Tezky bit.
Goldreich-Levinuv algoritmus a veta (s dk.).
Charakterizace PRNG pomoci nepredpoveditelnosti bitu (bez
dk.).
Interaktivni dukazove systemy.
Trida IP, a pozorovani: NP a coRP jsou casti IP.
Shamirova veta: IP=PSPACE (bez dukazu). Dukaz specialniho pripadu:
coNP je cast IP.
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, dk neaproximovatelnosti 3SAT.
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.
Temata, z nichz
ktera jsou probirana, je-li dost casu (ale nejsou zkousena):
Spodni odhady na velikost booleovskych obvodu:
monotoni obvody pro kliku (jen formulace), obvody konstantni
hloubky pro paritu (dukaz aproximacni metodou Razborov-Smolensky).
(Boppana-Sipser'89)
Komunikacni slozitost a Karchmer-Wigdersonova veta (dukaz).
Priklad: parita.
(Razborov'11)
"Natural proofs" Razborova a Rudiche a veta o jejich neexistenci (s dk.).
(Razborov-Rudich'99)
Efektivni interpolace pro rezoluci, tezko oddelitelne
disjunktni NP pary.
(Krajicek'97)
Pet svetu R.Impagliazza.
(Impagliazzo'95)
Literatura na webu:
skripta Stepana Holuba (cesky, obsahuji jen cast probirane latky)
Vynikajici je sbornik prednasek:
Steven Rudich, Avi Wigderson eds.:
Computational Complexity Theory,
AMS | PCMI, 2004, 389 pp..
Neni sice online, ale
vetsi cast je na
Google books a
nektere prednasky relevatni
k nasemu sylabu jsou jednotlive online tez:
Sanjeev Arora,
Exploring Complexity Through Reductions,
(obsahuje PCP a souvislost s neaproximovatelnosti)
Oded Goldreich,
Pseudorandomness - part I.
(casti 1 a 2 obsahuji material o vypoctni nerozlisitelnosti
distribuci, pseudonahodnych generatorech, vetu o prodlouzeni,
jednosmerne funcke a jejich tezky bit, konstrukce PRNG z OWP)
Luca Trevisan,
Pseudorandomness - part II.
(obsah neprobirame, ale nekoho to muze zajimat)
Salil Vadhan,
Probabilistic proof systems - part I.
(obsahuje Interactive proofs a Zero-Knowledge Proofs)
Madhu Sudan,
Probabilistic proof systems - part II
(obsahuje PCP)
Lecture notes z ruznych kursu a rukopisy knih
(finalni verse nejsou typicky online):
Boaz Barak's courses
(seznam obsahuje zakladni prednasky slozitosti a kryptografie)
a draft of Sanjeev Arora a Boaz Barak's book
"Complexity Theory: A Modern Approach".
(obsahuje vse probirane a velmi mnoho neprobiraneho,
bohuzel take hodne tiskovych i vecnych chyb
a nepresnosti, t.j. pouzivejte opatrne)
Jonathan Katz's course
(obsahuje mnoho probiraneho - P, NP, NP-uplnost,
pravdepodobnosti tridy, IP, zero-knowledge, PCP, ...,
ale typicky jen velmi strucne poznamky psane studenty
a jinak odkazuje k castem v Arora-Barak)
Oded Goldreich,
"Foundations of Cryptography"
a
"Computational Complexity: A Conceptual perspective".
(na strankach jsou k dosazeni rukopisy dvou jiz vyslych
knih - obsahuji skoro vse probirane a mnoho dalsiho materialu)
Toto jsou dve prednasky z kryptografie - z toho
neprobirame skoro nic, ale uvadim pro zajimavost
(druha prednaska obsahuje i material o OWF a PRNG
a o jejich pouziti).
Bellare-Rogaway course ("Introduction to Modern Cryptogtaphy")
Bellare-Goldwasser course (lecture notes on cryptography)