Bonyolultságelmélet előadás

Hely: D 3-110
Idő: hétfő  10:15-11:45, szünet nélkül

Első óra: szeptember 10.
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 majd a vizsgaidőpontok, elmaradó órák, 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) Novadat, 1999.


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. Nem szükséges ünneplőbe öltözni a vizsgára.

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).

A vizsga helye a Neptunban látható lesz majd.

 Volt:

Az Aho-Ullman-Yannakakis tétel. P és NP analógiái kommunkációs játékokra, ezek 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.

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

Lesz:

 

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 számítógépek, PRAM. 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.

Rendezés párhuzamosan PRAM-mel O(log² n) időben. Nem bizonyítjuk: Cole rendezése O(log n) időben.

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.

Elemkülönbözőség konstans 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.

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.

Ö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).

Szimmetrikus nemkonstans Boole függvény 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ól-definiáltság, invariancia tétel. A K(x) nem-rekurzív. Bizonyítás a megállási problémára. A Kolmogorov bonyolultság közelíthetetlensége.

Gödel nemteljességi tételének bizonyítása Kolmogorov bonyolultsággal.

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.

Egyirányú függvény és véletlenszám generátor viszonya. Kandidátusok egyirányú függvényre. négyzetgyökvonás prím és összetett modulussal.