Bonyolultságelmélet szeminárium

2020 Tavasz

Vezetők: 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. Elekes György terem


Hirdetmények


1. alkalom (II. 26.) Miklós István

"Tisztán kombinatorikai algoritmusok konstans deviációjú karakterekhez tartozó mátrix immanensek kiszámolására"

Legyen $A$ egy $n\times n$-es mátrix, $\lambda$ pedig egy irreducibilis karaktere az $S_n$ szimmetrikus csoportnak. Ekkor az $A$ mátrix $\lambda$-immanense
$$ Imm_{\lambda}(A) := \sum_{\sigma \in S_n} \lambda(\sigma) \prod_{i=1}^n a_{\sigma(i),i}. $$
Két közismert mátrix immanens a determináns és a permanens, rendre az előjel és a triviális karakterrel. Habár ez a két mátrix függvény nagyon hasonlít egymásra, a determináns polinomiális időben kiszámolható, míg a permanens kiszámolása \#P-nehéz.

Reprezentációelméletből tudjuk, hogy minden Young diagramhoz tartozik egy irreducibilis karakter. A determináns az $n$ sorú, soronként egy cellát tartalmazó $(1^n)$ Young diagramhoz tartozik, míg a permanens az egyetlen sorú $(n)$ Young diagramhoz tartozik. A Young diagram deviációján az első oszlopán kívül szereplő cellák számát értjük. Így a determináns a $0$ deviációjú karakterhez tartozó immanens, míg a permanens az $n-1$ deviációjú karaketerhez tartozó immanens. Azt sejtjük, hogy az immanensek számítási komplexitása a deviációval nő, és a permanensen túl néhány további nagy deviációjú karakterhez tartozó mátrix immanens kiszámítása is bizonyítottan nehéz.

Bürgisser megmutatta, hogy ha egy $A$ mátrix eleme a $GL_n$ csoportnak és $\lambda$ deviációja konstans (nem függ $n$-től), akkor $Imm_{\lambda}(A)$ kiszámolható polinom időben. Ebben az előadásban tisztán kombinatorikai algoritmusokat adunk meg tetszőleges mátrixokhoz és konstans deviációjú karakterekhez tartozó mátrix immanensek kiszámolására. Mivel az algoritmusunk osztásmentes, tetszőleges kommutatív gyűrű feletti mátrixokra is alkalmazható.

Az előadás megértéséhez nem szükséges ismerni a reprezentációelméletet, minden fogalmat definiálni fogunk. Továbbá ismertetjük, hogy az immanensek elmélete hogyan kapcsolódik további bonyolultságelméleti kérdésekhez, valamint olyan gráfelméleti témákhoz, mint a Tutte polinom, Hamilton körök, valamint a teljes párosítások.

Közös munka Cordian Rienerrel (University of Troms\o).

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


2. alkalom (IV. 29.) Kolok Csegő (interneten)

"A stratégialopás nem konstruktív"
Bodwin és Grossman cikke.

Sok kombinatorikai játékban használjuk a stratégialopás módszerét annak bizonyítására, hogy az első (kezdő) játékosnak van nyerő stratégiája. A cikk az ilyenfajta bizonyítások bonyolultsági hátterét vizsgálja: milyen nehéz egy játékban megtalálni egy adott állásban egy nyerő lépést, ha tudjuk stratégialopás alkalmazásával, hogy ilyen lépés létezik? Bizonyításra kerül, hogy Minimum Poset és a Szimmetrikus Maker-Maker játékokra, amik jelenleg a két főbb osztályát alkotják a stratégialopást felhasználó játékoknak, ez a probléma PSPACE teljes. Emellett a fent említett két játékosztályból néhány érdekes példa kerül bemutatásra.

Az előadást sávszélességtől illetve az adott eszköz felbontásától kétféle minőségben lehet megnézni:

Jó minőség, Google Drive.   ( A dia közepén alig látható "lejátszás" nyílra kell rákattintani.)

Gyengébb minőség, Youtube.   ( Az alsó fekete sor jobb szélén van a teljes képernyős módra váltás.)

Az előadás diái, lapozhatóan, pdf formátumban.