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.


TERV:


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

"A 3-összeg probléma"
Gronlund és Pettie cikke.


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

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


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

""
cikke.