Andó Szabolcs: 2-D Tucker PPA-teljes (Aisenberg, Bonet és Buss cikke)

Bonyolultságelmélet szeminárium

Absztrakt:

Tucker lemmája a híres Borsuk-Ulam topológiai tétel
kombinatorikus változata. Az ehhez kapcsolódó számítási
feladatról már Papadimitriou 1992-ben belátta, hogy a
PPA bonyolultsági osztályban van.  Ugyanebben a cikkben
azt is állította, hogy a PPA-nál szűkebb PPAD osztálynak
is tagja, ez azonban téves volt. Az előadás nagy
részében megnézzük annak a bizonyítását, hogy 2-D Tucker
PPA-nehéz, ezután megvizsgáljuk, hogy PPA-ban található,
vagyis összefoglalva PPA-teljes.  Ennek során arra is
kitérünk, hogy miért nem működik a fenti gondolatmenet
arra, hogy Tucker PPAD-ben lenne.

For Teams access please contact Zoltán Király (kiraly[at]cs.elte.hu).