Bursics Balázs: Tarski-fixpont keresése

Egyéni Kutatómunka 2

2021/22 II. félév

Témavezető:
Pálvölgyi Dömötör (ELTE TTK, Számítógéptudományi Tanszék)
Cím:
Tarski-fixpont keresése
Előadás:
---

Tarski fixponttétele szerint egy teljes hálón értelmezett monoton függvénynek mindig van fixpontja, ennek megtalálása az rács esetében érdekes keresési feladat, ami a PLS és PPAD bonyolultsági osztályokban is benne van. Ezzel kapcsolatban tervezek cikkeket feldolgozni, többek között Chen és Li frissen megjelent Improved Upper Bounds for Finding Tarski Fixed Points című cikkét. (Zólomy Kristóffal közösen.)