Bonyolultságelmélet előadás

Idő: kedd, 10:15-11:45, első óra: szeptember 13.

Hely: Déli tömb, 5-501 terem

Előadó: Grolmusz Vince

A szeptember 27-i előadást nem-jelenléti módon tartjuk meg.

A szeptember 27-i előadást az üzenetben kapott jelszóval itt lehet megnézni.


Az előadás látogatása nem kötelező, azonban a vizsga anyaga minden, ami az előadáson elhangzik. Kötelező azonban ezt a honlapot rendszeresen figyelemmel kísérni, itt jelennek meg az esetleg elmaradó órák, vagy egyéb hirdetmények.


A legfontosabb két könyv:

Lovász László: Algoritmusok bonyolultsága, jegyzet, ez on-line itt van.
Papadimitriou: Algoritmusok bonyolultsága, (egyetemi tankönyv)


A vizsga anyaga minden, ami az előadáson elhangzik. Az ajánlott irodalomban minden elhangzott tétel megtalálható,
sokszor azonban más, hosszabb, bonyolultabb bizonyítással. Vizsgán természetesen akármilyen helyes bizonyítást  elfogadok.

Jelentkezni a Neptunban lehet.

Az ezen oldalon levő tematikából kap mindenki két tételt, távolabb levő helyekről.

A sikeres vizsga feltételei:

A két kiadott tétel alapos ismerete, különösen:

A definíciók és a tételek pontos ismerete.   A tétel bizonyításában

  • lényeges eredmény elérése a kettes,
  • a bizonyítás lényegében történő befejezése nagyobb hiánnyal  a hármas,
  • apró hiánnyal a négyes,
  • hiánytalanul az ötös szinthez.

Hiányosság a definíciókban illetve a tételek kimondásában nem megengedett (azaz rögtön elégtelen a hibás definíció illetve
állítás kimondása).

Volt:

Kommunikációs játékok, Mehlhorn-Schmidt tétele (ismétlés)

Nem-determinisztikus kommunikációs bonyolultság. Randomizált kommunikációs bonyolultság.

Példák nem-triviális kommunikációs protokollokra: Fák metszete, teljes részgráf és üres részgráf metszete.

A P, NP, co-NP analógjai a kommunikációs játékokra Pcc, NPcc, co-NPcc, ezek relációi.

Az Aho-Ullman-Yannakakis tétel.

A polinomiális hierarchia.  Polinomiális reláció. A Σ_i és Π_i nyelvosztályok.

Az EXACT_INDEPENDENT nyelv Σ_2-ben van.

Ha Σ_i = Π_i akkor a PH összeomlik az i. szintre.

PSPACE. Savitch tétele. NPSPACE=PSPACE.

Σ_i és Π_i  teljes nyelvek. Mi lenne, ha lenne PH-teljes nyelv?

A PH PSPACE-ben van.

A TQBF nyelv. A TQBF PSPACE-teljes.

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

Interaktív játékok és bizonyítások; alkalmazás a gráf-izomorfizmus problémára.

Lesz:

Az IP osztály.  IP PSPACE-ben van.

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. RP NP-ben van,  P/poly. Adleman tétele: RP P/poly-ban van. .

Berman tétele az unáris NP-teljes nyelvekről.  Fortune tétele, Mahaney tétele.

ZPP, BPP. BPP ⊆ Σ_2 ∩ Π_2.

Boole hálózatok. Minden Boole függvény kiszámolható három mély Boole-hálózattal.

BPP ⊆ P/poly.

A P/poly osztály és a polinomiális méretű Boole hálózatok viszonya.

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.

Thompson tétele az ID függvény VLSI csippel való kiszámolására,  terület-idő trade-off.

Párhuzamos algoritmusok. MAX kiszámítása n² processzorral O(1) lépésben; MAX kiszámítása n processzorral O(log log n) lépésben.

Párhuzamos számítógépek, PRAM.

Skalárszorzás, mátrixszorzás párhuzamosan.

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.

Elemkülönbözőség konstans időben.

Rendezés párhuzamosan PRAM-mel O(log² n) időben.

Nem bizonyítjuk: Cole rendezése O(log n) időben.

Összeadás párhuzamosan: PRAM-mel és trittekkel; Boole hálózattal. Szorozni nem lehet konstans időben és polinomiális méretben.

Összehasonlító hálózatok. A 0-1 szabály.

Batcher sort.

Nem bizonyítjuk: Ajtai-Komlós-Szemerédi rendezőhálózata.

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)≤ D_0(f)D_1(f).

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.