Bonyolultságelmélet szeminárium

2016 Ő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


1. alkalom (IX. 28.) Pálvölgyi Dömötör

"Bevezetés a PPA osztályba"

Papadimitriou 94-es cikkében számos új TFNP-beli (keresési) bonyolultsági osztályt definiált, melyekről itt lehet olvasni: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#ppa

A legfontosabbnak a PPAD tűnt, kiderült, hogy PPAD-teljes a SPERNER, a BORSUK-ULAM, a NASH és még sok más fontos keresési probléma. Aztán tavaly kiderült, hogy a BORSUK-ULAM mégsem, mert az eredeti cikkbe csúszott egy kis hiba, ez így PPA-teljes lett. Most emiatt kicsit a PPA került előtérbe, egy friss eredmény alapján ebben van a faktorizáció is (ha igaz az általánosított RH).

Előadásom célja, hogy bemutassam az alapokat, majd a legújabb eredményeket a gráfokhoz kapcsolódó problémákról, például a 2D-SPERNER PPAD-teljességének bizonyítását. A 2D-SPERNER keresési feladatban egy 2^n x 2^n méretű rács csúcsai vannak három színnel színezve úgy, hogy a bal-alsó sarok 1-es, a többi alsó oldali pont 2-es és a többi oldalsó pont 3-as szinű. A keresési feladat egy, a Sperner-lemma által garantált, háromszínű kisnégyzet megkeresése. Ezután azt is megnézzük, hogy a 2D-TUCKER miért lesz viszont csak PPA-teljes, meg mondok pár nyitott kérdést.


2. alkalom (X. 12.) Aleksziev Rita

"Egyenlőség ellenőrzése kommunikációs gráfokban"
Alon, Efremenko és Sudakov cikke.

Adott egy G(V,E) összefüggő irányítatlan gráf, amelynek k csúcsa van. A csúcsokon áll egy-egy játékos, mindenkinek van egy n bites száma. Egy determinisztikus kommunikációs protokoll segítségével kell eldönteniük, hogy mindenkinél ugyanaz a szám van-e. A játékosok csak a szomszédjaikkal kommunikálhatnak. Legkevesebb hány bit továbbításával tudják ezt megtenni? A cikk az f(G)=lim f(n,G)/n értékre ad alsó és felső korlátot, ahol f(n,G) a G gráf esetén elküldendő bitek minimális számát jelöli n hosszú inputokra.


3. alkalom (XI. 9.) Tóthmérész Lilla

"A chip-firing játék bonyolultságelméleti kérdései"

A chip-firing a következő egyszemélyes játék: adott egy irányított gráf, és minden csúcsán néhány chip. Ha egy csúcson legalább annyi chip van mint a csúcs ki-foka, akkor kilőhetjük ezt a csúcsot, ami azt jelenti, hogy minden rá-illeszkedő ki-élen átadunk egy chip-et. Ha valamikor egyik csúcsot sem tudjuk lőni, akkor azt mondjuk, hogy a játék leállt. Ennek a látszólag egyszerű játéknak a matematika sok területével van kapcsolata. Az előadásban főleg algoritmikus kérdésekről lesz szó. Két alap algoritmikus kérdés a következő: 1. Adott egy kezdeti chip-kiosztás, ebből elkezdve a játékot, biztosan leáll-e a játék véges sok lépés után (megállási probléma)? 2. Adott két chip-kiosztás esetén el tudunk-e jutni az egyikből a másikba (elérhetőségi probléma)? Ezekről a kérdésekről meglepő módon nem triviális hogy NP-ben vagy co-NP-ben vannak-e, de ki fog derülni hogy az első NP-beli, a második pedig co-NP -beli. A megállási problémáról ismert hogy nehéz, az elérhetőségiről nem. Ezen kívül bizonyos speciális esetekben ismert vagy sejtett hogy ezek a problémák P-ben vannak.

Björner és Lovász, Farrell és Levine, ill. Hujter, Kiss és Tóthmérész cikkei alapján.


4. alkalom (XII. 14.)

100 years of matching theory in Hungary