- Előadó: Lovász László
- Előadás helye: Déli Tömb 0.818, ideje: csütörtök 10:15-11:45
Az előadás témáját leginkább ez az angol jegyzet közelíti meg.
Hetenkénti téma
Szeptember 16
Véletlent használó algoritmusok: polinomazonosság tesztelése, prímtesztelés.Szeptember 23
Randomizált Turing gépek és az általuk definiált bonyolultsági osztályok. Információs (Kolmogorov) bonyolultság fogalma. Függetlensége az univerzális Turing-géptől.Szeptember 30
Kolmogorov-bonyolultság kiszámíthatalansága és ennek kapcsolata az írógép-paradoxonnal. Kolmogorov bonyolultság közelítő kiszámíthatósága.Október 7
A véletlen sorozat infomációelmélet fogalma. Majdnem minden sorozat véletlen, minden véletlen sorozat kielégíti a nagy számok törvényeit. Példák optimális Kolmogorov-kódra.Október 14
Véletlen-szám generátorok. Klasszikus konstrukciók: eltolás-regiszter, lineáris kongruencia generátor, irracionális szám számjegyei. Biztonság és megjósolhatatlanság, ezek ekvivalenciája.Október 21
Biztonságos véletlenszám-generátor konstrukciója (Goldreich-Levin), egyirányú függvények és permutációk.November 4
Kriptográfia elemei. One-time pad, ennek biztonsága. Nyilvános kulcsú titkosírás. Az RSA-kód. Döntési fák: példák döntési fát használó algoritmusra.November 11
Döntési fák: determinisztikus és nem-determinisztikus bonyolultság, kapcsolatuk egymással és a normálformákkal.November 18
Zárkózott Boole-függvények. Kommunikációs bonyolultság definíciója, kommunikációs mátrix, protokoll-fa.November 25
Kommunikációs bonyolultság. Példák, rang-korlát, nem-determinisztikus bonyolultság, determinisztikus bonyolultság felső becslése a nem-determinisztikusok szorzatával.December 2
Interaktív bizonyítások. Utolsó lépés borítékolása, Hamilton-kör létezésének bizonyítása a kör megadása nélkül.December 9
Interaktív bizonyítás co-NP-beli problémákra, PSPACE-beliekre csak kimondva. PCP-tétel (csak kimondva).December 16
Alkalmazás: ha P nem=NP, akkor a maximális teljes részgráf nem közelíthető.