Bonyolultságelmélet előadás

Kommunikációs játékok, kommunikációs komplexitás, kommunikációs mátrix. A Mehlhorn-Schmidt tétel. Nemdeterminisztikus kommunikációs komplexitás, ennek jellemzése fedő téglalapokkal. Simon-Rabin protokoll: egy véletlent használó eljárás az ID függvény kiszámítására.

Thompson  tétele VLSI tervezésre.  Az Aho-Ullman-Yannakakis tétel. A P, NP, co-NP kommunikációs megfelelői között fennálló viszony. A Karchmer-Wigderson tétel.


A TQBF nyelv. A TQBF PSPACE-teljes.

A Generalized Geography játék. A Generalized Geography szintén PSPACE-teljes.

Az IP osztály. Shamir tétele: IP=PSPACE, a bizonyítás részei: (1) egyszerű kvantifikált formulák, minden formula polinomiális időben ilyenné alakítható, (2) formulák aritmetizálása, ha A egy n hosszú formula aritmetizáltja, akkor van olyan p prím, hogy 2^n<p<2^{2n}, és A mod p nem nulla, (3) a protokoll és hibabecslés.

Zero Knowledge Proofs, példák: gráf-nemizomorfizmus, Hamilton-kör.

Véletlen bonyolultsági osztályok: RP, ZPP, BPP. BPP \subseteq \Sigma_2 \cap \Pi_2.

Boole hálózatok. Minden Boole függvény kiszámolható három mély Boole-hálózattal. A P/poly osztály és a polynomiális méretű Boole hálózatok viszonya. BPP \subseteq P/poly.

A PARITY-t d mélységű Boole hálózattal csak legalább exp(n^{1/(cd)}) mérettel lehet kiszámolni: a bizonyítás lépései: (1) aritmetizálás (2) a nagyfokú VAGY-ok lecserélése közelítő, kisfokú VAGY-okra, (3) kisfokú polinom nem közelítheti jól az összes Boole függvényt.

Párhuzamos számítógépek, PRAM. Párhuzamos algoritmusok. MAX kiszámítása n^2 processzorral O(1) lépésben; MAX kiszámítása n processzorral O(log log n) lépésben. Skalárszorzás, mátrixszorzás párhuzamosan.   Elemkülönbözőség konstans időben.  Rendezés n processzorral O(\log^2 n) időben.  Súlyozott élű gráfban minden csúcspár közötti legrövidebb utak számítása párhuzamosan. Csánky tétele: A determináns számítása párhuzamosan. Ezzel páros gráfban teljes párosítás létének ellenőrzése. Feszítőerdő keresés párhuzamosan.
Rendezés párhuzamosan PRAM-mel O(log^2 n) időben.  Nem bizonyítjuk: Cole rendezése O(log n) időben.

Összehasonlító hálózatok. A 0-1 szabály. Batcher sort. Nem bizonyítjuk: Ajtai-Komlós-Szemerédi rendezőhálózata.

Konstans mélységű, polinomiális méretű hálózat két n bites szám összeadására. A szorzásra nem létezik ilyen.

Algebrai döntési fák, alsó becslés a konvex burok feladatra komponens-számlálással lineáris tesztfüggvényeket tartalmazó fára és d. fokú polinom tesztfüggvényekre is a Milnor-Thom tétellel.

Egyszerû döntési fák. Zárkózott gráftulajdonságok. Az összefüggőség  zárkózott. Izolált pont létezése egy gráfban zárkózott, erre D_0 és D_1 kiszámítása. Determinisztikus és nem-determinisztikus döntési fa bonyolultság, egyenlőtlenségek. Tardos tétele: D(f)\leq D_0(f)D_1(f).

Szimmetrikus nemkonstans Boole fv zárkózott.

Ha f egy N elemű halmazon veszi fel az 1 értéket, és N=2^k M, ahol M már páratlan, akkor az f-et kiszámoló bármely egyszerű döntési fa mélysége legalább n-k.

Minden nem-konstans szimmetrikus Boole-függvény zárkózott. Gyenge szimmetria. Aanderaa-Karp-Rosenberg sejtés.

Kolmogorov komplexitás. Definíció, jóldefiniáltság, invariancia tétel. A K(x) nemrekurzív. Bizonyítás a megállási problémára. A Kolmogorov bonyolultság közelíthetetlensége. Informatikusan véletlen sorozat. Informatikusan véletlen a végtelen 0-1 sorozat, ha elemeit függetlenül, egyenletes eloszlással generáltuk. Számítógép nem tud informatikusan véletlen sorozatot generálni.

Pszeudovéletlen sorozatok. Klasszikusok: eltolás-regiszter; lineáris kongruencia-generátor. Generátor, sikeres teszt, biztonságos véletlenszám-generátor fogalma. Ha P=NP, akkor nincs biztonságos polinomiális idejű véletlenszám-generátor.Megjósolhatatlan véletlenszám generátor (next bit test). Yao tétele: egy generátor pontosan akkor megjósolhatatlan, ha biztonságos.