Idő: hétfő, 16:00-17:30, első óra: 2025. szeptember 8.
Hely: Déli tömb, 1. emelet, 1–820 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:
Az Aho-Ullman-Yannakakis tétel kommunikációs játékokra. P^CC, NP^CC és co-NP^CC viszonya.
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.
Σ_i és Π_i teljes nyelvek. Mi lenne, ha lenne PH-teljes nyelv?
PSPACE. A PH PSPACE-ben van.
Savitch tétele. NPSPACE=PSPACE.
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.
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, következmények.
Páros gráfban teljes párosítás létének ellenőrzése determinánssal párhuzamosan.
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 tritekkel;
Boole hálózattal.
Szorozni nem lehet konstans időben és polinomiális méretben.
Elemkülönbözőség konstans időben.
Thompson tétele az ID függvény VLSI csippel való kiszámolására, terület-idő trade-off.
Ö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.
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.
Egyirányú függvény és véletlenszám generátor viszonya (nem bizonyítjuk). Kandidátusok egyirányú függvényre. négyzetgyökvonás prím és összetett modulussal, szorzás.
Kolmogorov bonyolultság. Jóldefiniáltság, invariancia tétel. A K(x) nem rekurzív. Egy közelíthetetlenségi tétel.
Informatikusan véletlen sorozat. Számítógép nem tud informatikusan véletlen sorozatot generálni.