Bonyolultságelmélet előadás

Idő: szerda, 14:10-15:40, első óra: szeptember 11.

Hely: Déli tömb, 4-202 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).

………………………………………

Volt:

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.

BPP ⊆ 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 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.

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.

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

Lesz:

 

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.

……