Vidnyánszky Zoltán: CSP Dichotómia a Borel esetben

ELTE Analízis tanszék szemináruma

Absztrakt: A Bulatov-Zhuk-féle CSP Dichotómia a számítástudomány utolsó évtizedének egyik legfontosabb eredménye. Azt mondja ki, hogy egy H véges relációs struktúrára annak eldöntése, hogy egy G véges struktúrának van-e homomorfizmusa H-ba vagy polinomiális vagy NP-teljes nehézségű. Az előadásomban ennek a kérdésnek a Borel verzióját vizsgálom majd: pontosabban, adott G Borel struktúrára szeretnék eldönteni, hogy van-e egy fix véges H-ba Borel homomorfizmusa. Meglepő módon kiderül, hogy a Borel esetben vannak olyan H struktúrák, melyekre a probléma nehéz, míg a véges probléma polinomiális időben eldönthető.