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


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.


TERV:


4. alkalom (XI. 5.) Árendás Péter

"Számítások megtelt memóriával"
Buhrman, Cleve, Kouckry, Loff és Speelman cikke.


5. alkalom (XI. 19.) Papp László

"Cikk-cakk rendezés"
Goodrich cikke.


6. alkalom (XII. 3.) Király Csaba

"Rövid programok lineáris lista-approximációja"
Bauwens és Zimand cikke.