Leírás
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ás az interenten lesz persze, pontos hozzáférést a
https://web.cs.elte.hu/~kiraly/bonyszem20tav.html
oldalon közlünk, illetve levélben is szétküldjük.
Az előadás ideje alatt (10:15--13:00) lehet az előadótól sype-on, vagy akár
emailben is kérdezni.
A mai előadás felvételének linkje:
https://drive.google.com/file/d/1r4cwMno-EjnimfjZ8s0nIpu7U47qkN9u/view?usp=drive_web
A felvétel bármikor megnézhető, megállítható és visszatekerhető.
Akinek kicsi a sávszélessége, és rosszabb minőséget is elfogad:
https://youtu.be/vZ2sG-lBkug