Idő: csütörtök, 14:00-15:30, első óra: szeptember 14.
Hely: Déli tömb, 3-110 terem
Előadó: Grolmusz Vince
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önyvek:
Lovász László: Algoritmusok bonyolultsága, jegyzet
Arora-Barak: Computational Complexity: A Modern Approach
Papadimitriou: Algoritmusok bonyolultsága, (egyetemi tankönyv)
A vizsgáról:
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).
………………………………………
Vizsgatematika:
Kommunikációs játékok, Mehlhorn-Schmidt tétele Nem-determinisztikus kommunikációs bonyolultság. Randomizált kommunikációs bonyolultság. (ismétlés)
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.
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.
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.
Rendezés párhuzamosan PRAM-mel O(log² n) időben.
Nem bizonyítjuk: Cole rendezése O(log n) időben.
Elemkülönbözőség konstans időben.
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.
Összeadás párhuzamosan: PRAM-mel és tritekkel;
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.