- Előadó: Lovász László
- Előadás helye: Déli Tömb 7.103, ideje: csütörtök 10:15-11:45
- Első előadás: szeptember 10.
Az előadás témáját leginkább ez az angol jegyzet közelíti meg.
Hetenkénti téma
Szeptember 10
Véletlent használó algoritmusok: polinomazonosság tesztelése, prímtesztelés.Szeptember 17
Prímtesztelő algoritmus elemzése. Randomizált Turing gépek és az általuk definiált bonyolultsági osztályok: BPP,RP,Delta-RP és kapcsolatuk.Szeptember 24
Információs (Kolmogorov) bonyolultság fogalma. Függetlensége az univerzális Turing-géptől. Kiszámíthatalansága és ennek kapcsolata az írógép-paradoxonnal.Október 1
Kolmogorov bonyolultság közelítő kiszámíthatósága. A véletlen bonyolultságelméleti fogalma. Informatikusan véletlen sorozat.Október 8
Kód tömörsége, polinomiális kód, példák: k elemű részhalmazok, számozott fák, Prüfer kód).Október 15
Pszeudovéletlen sorozatok, klasszikus generátorok (eltolás-regiszter, lineáris kongruencia generátor, irracionális szám számjegyei). Biztonságos (polinom idejű) véletlenszam generátor. Ha P=NP akkor ilyen nincs. Yao tétele a next bit teszt általanosságáról. Egyirányú függvények és pszeudovéletlen generátorok, egyirányú permutáció. Pszeudovéletlen generátorból egyirányú függvény. Egyirányú permutációból véletlenszám-generátor (Goldreich-Levin lemmájával).Egyirányú függvény jelöltek. Négyzetgyökvonás modulo primszám.
Október 22
Kriptográfia. One-time pad, ennek biztonsága. Diffie-Hellman protokoll titkos kulcs megosztására. A Hamilton-körös titkosírás banki műveletekhez. Nyilvános kulcsú titkosírás. Az RSA-kód. Az RSA feltörése, ha ugyanazt a modulust többen használják. Titokmegosztás: Shamir módszere es egy optikai eljárás.November 5
Döntési fák. Barkochba. Rendezés döntési fán. Információelméleti alsó becslés. Algebrai döntesi fák. A Konvex burok feladat; az elemkülönbözőségi feladat. Alsó korlát az összefüggő komponensek számán keresztül.November 12
Nem-determinisztikus döntési fák. Példák: összefüggőség, izolált pont. Kapcsolatuk a determinisztikus döntési-fa bonyolultsággal.Zárkózott tulajdonságok, összefüggőség zárkózott. Szimmetrikus és gyengén szimmetrikus gráftulajdonságok. Abszolút győztes létezése nem zárkózott.
November 19
Elégséges feltételek zárkózottságra. Minden gyengén szimmetrikus, nem-konstans monoton Boole-függvény prím számú változóval zárkózott.Kommunikációs bonyolultság fogalma, a feladat kitűzése mátrix-szal. Rang-feltétel. Példák: részfa diszjunktsága, teljes és üres részgráf diszjunktsága.
November 26
Nem-determinisztikus kommunikációs bonyolultság, példa: konvex sokszögek diszjunktsága. Az Aho-Ullman-Yannakakis Tétel. Randomizált protokoll az egyenlőség eldöntésére. P és NP kommunikációs bonyolultság esetén.Interaktív bizonyítások: egyszerű példák, Hamilton-kör létezésének bizonyítása a kör megadása nélkül.
December 3
Interaktív bizonyítás co-NP-beli problémákra, PSPACE-beliekre csak kimondva. PCP-tétel (csak kimondva).December 10
Alkalmazás: ha P nem=NP, akkor a max. teljes részgráf nem közelíthető.