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.


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.

A Clique vs. Independent Set (CIS) probléma a következő: adott egy n csúcsú gráf és két játékos, Alice és Bob. Mindkettőjük kap egy cetlit, amin a gráf csúcsainak egy-egy részhalmaza szerepel, Alice-én egy klikk, Bob-én pedig egy független halmaz. Azt kell eldönteniük minél kevesebb bitnyi kommunikációval, hogy van-e közös csúcsa ennek a két halmaznak. A cikk ennek a feladatnak a coNP változatát ( coNP^{cc}(CIS) ) vizsgálja, és erre ad egy új, szuperlogaritmikus alsó becsést. Az eddigi legjobb alsó becslés 2*log n volt.


6. alkalom (IV. 22.) Pálvölgyi Dömötör

"Determinisztikus kommunikáció és a partíciós szám"
Göös, Pitassi és Watson cikke.

A múlt heti cikk egy nagyon friss javításáról lesz röviden szó. Egy kommunikációs mátrix partíciós száma chi(M) a legkisebb k, amire M partícionálható k db konstans részmátrixra. Régóta ismert, hogy a det. komm. bonyolultságra alsó becslés a log(chi(M)). Megmutatják, hogy van olyan M feladat, melyre
Omega~(log^{1.5}(chi(M))) is alsó becslés, másrészt olyan is, ahol
Omega~(log^2(chi_1(M))) alsó becslés, itt chi_1(M) a legkisebb k, amire M egyesei partícionálhatóak k db csupa-1 részmátrixra. Tehát ebből már következik, hogy a CLIQUE-VS-INDEPENDENT-SET-re kellhet
Omega~(log^2 n) bit kommunikáció.


7. alkalom (V. 6.) Tóthmérész Lilla

"Karp- és Turing-teljesség szétválasztása"
Mandal, Pavan és Venugopalan cikke.

Az NP-teljességet Karp-redukcióval szokás definiálni, de Turing-redukcióval definiálni is legalább ilyen szemléletes lenne. Kérdés hogy a két fajta redukció szerinti NP-teljes nyelvek megegyeznek-e. Korábbi cikkekben már viszonylag erős feltevések mellett megmutatták, hogy létezik Turing-redukcióval NP-teljes, de Karp-redukcióval nem NP-teljes nyelv. A cikk ezt egy gyengébb feltevés mellett mutatja meg.