Bonyolultságelmélet szeminárium

2014 Ősz

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 (IX. 17.) Marx Dániel

"Dichotómiatételek gráfproblémákra"

Dichotómiatétel alatt olyan eredményt értünk, amely egy adott problémacsalád bonyolultságát karakterizálja, minden egyes problémáról megmutatva, hogy 'egyszerű' vagy 'nehéz'. Például ilyen eredmény Hell és Nesetril klasszikus tétele, amely a H-színezés probléma bonyolultságát karakterizálja minden rögzített H gráf esetén: a probléma polinomidőben megoldható, ha H páros gráf, és a probléma NP-nehéz minden nem páros gráf esetén. Léteznek olyan dichotómia tételek, ahol a problémacsalád általánosabb módon van definiálva: a problémacsalád egy problémáját nem egyetlen gráf rögzítésével, hanem egy (esetleg végtelen) gráfosztály rögzítésével kapjuk. Például Yannakakis egy eredménye a csúcstörlési problémák bonyolultságát karakterizálja minden csúcstörlésre zárt osztály esetén, illetve Grohe egy eredménye karakterizálja a gráfhomomorfizmus probléma bonyolultságát abban az esetben, ha megköveteljük, hogy a 'bal oldali gráf' egy adott gráfosztályba tartozik. Az előadásban klasszikus és újabb gráfelméleti dichotómiatételeket tekintünk át.

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


2. alkalom (X. 1.) Kisfaludi-Bak Sándor

BETEGSÉG miatt elhalasztódott az 5. alkalomra. "Szubkvadratikus algoritmus a 3SUM problémára"
Gronlund és Pettie cikke.


3. alkalom (X. 15.) Tóthmérész Lilla

"Konstans rangú bimátrix játékok PPAD-teljesek"
Mehta cikke.

Ismert hogy a Nash-egyensúly kiszámítása egy bimátrix játékban PPAD-teljes. Egy A ill B kifizetési mátrixú bimátrix játék rangját rang(A+B)-ként definiálják. A rang pontosan a 0 összegű játékokra egyenlő nullával. Így 0 rangú játékokon a Nash-egyensúly polinom időben számolható. Később ez kiderült 1 rangú játékokról is. A cikkben bizonyítják, hogy a legalább 3 rangú játékokon viszont már PPAD-teljes a rang kiszámítása (a 2 rangú eset nyitva marad). A bizonyításban fixpont-keresési feladatokat használnak.


4. alkalom (XI. 5.) Király Csaba

"Rövid listák, rövid programokkal"
Bauwens és Zimand cikke.

Egy c-rövid program egy x szóra egy C(x)+c hosszú program az U univerzális Turing-gépre, melyet futtatva a kimenet x, ahol C(x) az x Kolmogorov bonyolultsága. Jól ismert, hogy a Kolmogorov bonyolultság kiszámíthatatlan, sőt még olyan kiszámítható nem korlátos függvényt se lehet adni, mely alulról korlátozza. Beigel és társszerzői a Kolmogorov-bonyolultság lista-approximálhatóságát vizsgálták, melyben egész számok olyan rövid listáját szeretnénk konstruálni, mely tartalmazza x Kolmogorov bonyolultságát. Belátták, hogy létezik olyan a konstans, melyre igaz, hogy nem számítható ki |x|/a-nál rövidebb lista.

Ezen negatív eredmények tükrében igen meglepőek az alábbi eredmények: Bauwens, Mahklin, Vereshchagin és Zimand valamint Teutsch bizonyították, hogy létezik olyan c konstans, melyre lehetséges polinomidőben egy olyan, x hosszában polinomiális sok programból álló listát adni, mely tartalmaz egy c-rövid programot. Az előadásomban elsőnként ezt bizonyítom, Zimand egyszerűsített leírását követve. Bauwens és Zimand belátták, hogy log(|x|)-rövid programot tartalmazó listából |x|-ben lineáris hosszúságú is konstruálható randomizált algoritmussal (itt az elkészítés ideje nem polinomiális), illetve log(|x|)^2-rövid programot tartalmazó lineáris hosszú listát polinomidőben készíthetünk (szintén randomizált algoritmussal). Az előadás második részében ezt az eredményt ismertetem.


TERV:


5. alkalom (XI. 19.) Kisfaludi-Bak Sándor

"Szubkvadratikus algoritmus a 3SUM problémára"
Gronlund és Pettie cikke.

A 3SUM problémában az input n darab valós szám, és el kell dönteni, hogy van-e köztük 3 olyan, melyek összege 0. A cikk megcáfolja a régóta fennálló sejtést, miszerint a triviális O(n^2) idejű algoritmus futásideje optimális.

A problémára adunk majd egy O(n^1.5 log^0.5 n) mélységű döntési fát, egy O(n^2 (loglog n/log n)^(2/3)) idejű determinisztikus, és egy O(n^2 (loglog )^2 / log n) idejű randomizált algoritmust. Ezután megvizsgálunk még néhány kapcsolódó problémát is, amelyekre hasonló módszerrel adhatók újabb algoritmusok.


6. alkalom (XII. 3.) Árendás Péter

"Párhuzamos rendezés"
Cole cikke.