Bonyolultságelmélet szeminárium

2015 Tavasz

Vezetők: Grolmusz Vince, Friedl Katalin, Pálvölgyi Dömötör, Király Zoltán

Minden második héten, Szerda 10:15-13:00
Pázmány Péter sétány 1/C. 3.607


Hirdetmények


Ajánlott irodalom


1. alkalom (II. 11.) Papp László

"Cikk-Cakk rendezés"
Goodrich cikke.

Cikk-Cakk rendezés: Determinisztikus "adat felejtő" (data-oblivius) rendező algoritmus O(n log(n)) időben.

Ismert tény, hogy egy n hosszú listát O(n log(n)) idő alatt tudunk determinisztikusan sorosan rendezni. Sokáig kérdéses volt, hogy létezik-e O(n log(n)) lépést használó hatékonyan párhuzamosítható rendezés. 1983-ban az Ajtai, Komlós és Szemerédi által készített AKS rendező hálózat adta meg erre a pozitív választ. Sajnos az AKS és eddigi javításai a gyakorlatban használhatatlanok mivel bár a mélységük O(log(n)), a tényleges műveletszám ~10.000.000 n log(n).

A rendező hálózatok rendelkeznek azon pozitív tulajdonsággal, hogy "adat felejtő"-ek: Az algoritmus memória hozzáférési sorozatai azonos hosszúságú bemenetek esetén azonosak. Így a memória hozzáférések - a bemenet hosszától eltekintve - függetlenek a bemeneti adattól. Így az AKS volt sokáig a legjobb ismert O(n log(n))-es "adat felejtő" rendező algoritmus is.

A Goodrich által készített Cikk-Cakk rendező hálózat a Shellsort és az AKS ötleteit használja. Az általa igényelt műveletszám ~10.000 n log(n), mely kevesebb az AKS műveletszámánál. Bár O(n log(n)) mélységű, így nem párhuzamosítható hatékonyan, ennek ellenére érdekes, mivel jelenleg ez az ismert legkevesebb műveletet igénylő "adat felejtő" rendező algoritmus.

Az előadás után cikkosztás volt.


2. alkalom (II. 25.) Kovács Erika

"Hálózatok kapacitásának közelíthetetlensége lineáris hálózati kóddal"
Lovett cikke.

A hálózati kódolás egy információküldési eljárás, mely lehetővé teszi, hogy egy hálózat belső pontjai a különböző csúcsokból beérkező üzeneteknek valamilyen függvényét továbbítsák. Aszerint, hogy ezen függvények milyen halmazból kerülhetnek ki, definiálhatunk általános- és lineáris hálózati kódokat. Ez utóbbiak a küldött üzeneteket egy vektortér elemeiként kezelik, és mindig valamilyen lineáris kombinációjukat továbbítják.

Ismert, hogy bizonyos üzenetküldési feladatoknál a lineáris kódok optimálisak (pl. aciklikus gráfok, egy forrás, több terminálpont esete [Jaggi et al.] ), de arra is akad példa, amikor bizonyítottan nem, mivel az általános hálózati kódokkal nagyobb kapacitás érhető el (pl. több forrás-terminál pár esetén [Dougherty et al.]).

Természetesen adódik a kérdés, hogy az általános hálózati kódolással elérhető kapacitás közelíthető-e a lineáris kódok kapacitásával? A cikk fő eredménye, hogy ilyen közelítés semmilyen konstanssal sem lehetséges.


3. alkalom (III. 11.) Papp László

"Numerikus fekete-fehér játékok bonyolultságelméleti vizsgálata"
Fenner, Grier, Messner, Schaeffer és Thierauf cikke.

Egy kombinatorikus játékot fekete-fehérnek nevezünk ha egy állásból a két játékos számára csak különböző lépések állnak rendelkezésre. Ilyen például a sakk, a dáma vagy a go. Továbbá egy játék numerikus ha a játék állásai megfeleltethetőek valós számoknak, valamint az állásokon a számokhoz hasonlóan értelmezhetőek műveletek.

Azt meghatározni, hogy egy kombinatorikus játék esetén melyik félnek van nyerő vagy nem vesztő stratégiája sokszor algoritmikusan nehéz.
A numerikus fekete-fehér játékok esetében erről a feladatról eddig annyit tudtunk, hogy NP-nehéz. Míg bizonyos nem numerikus fekete-fehér játéknak eddig is ismert volt PSPACE-teljessége. A cikk fő eredménye, hogy bizonyos fekete-fehér poset játékokról belátják, hogy numerikusak és PSPACE-teljesek is.

Ezen túl a cikkben megvizsgálnak egyéb fekete-fehér játékokat is, melyekről szintén érdekes állításokat igazolnak.


4. alkalom (III. 25.) Kisfaludi-Bak Sándor

"A K-kör probléma kernelizálása algebrai módszerekkel"
Magnus Wahlström cikke.

Az előadáson Magnus Wahlström "Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem" című cikkét dolgozom fel. A K-kör problémában azt kell eldöntenünk egy egyszerű gráfban, hogy egy rögzített K csúcshalmazon át található-e kör a gráfban. Erre a problémára fogunk adni egy általánosított kernelt, melynek mérete O(|K|^3), amely azért meglepő, mert két nagyon hasonló problémára (k-kör és rendezett K-kör probléma) nincs polinomiális általánosított kernel, feltéve, hogy a polinomiális hierarchia nem omlik össze.


TERV:

5. alkalom (IV. 15.) Herscskovics Dávid

"Alsó becslés a Klikk-Független diszjunktság nemdeterminisztikus kommunikációs bonyolultságára"
Göös cikke.


6. alkalom (IV. 29.) Tóthmérész Lilla

"A Turing- és a Karp-redukció szétválasztása"
Mandal, Pavan és Venugopalan cikke.


7. alkalom (V. 13.) Király Csaba

"TBA"
cikke.