See by year See by month Jump to month

Vidnyánszky Zoltán: CSP Dichotómia a végtelen esetben

 Download as iCal file
Wednesday, 11. December 2024, 10:10 - 11:10
A Bulatov és Zhuk által bizonyított CSP Dichotómia a számítástudomány utolsó néhány évének egyik legfontosabb eredménye. Azt mondja ki, hogy ha adott egy véges struktúra H, akkor annak eldöntése, hogy egy G struktúrának van-e H-ba homomorfizmusa vagy egyszerű (P-ben van), vagy nehéz (NP-teljes).

Először a tétel Borel verziójáról beszélek majd: itt H még mindig véges, de a G már Borel struktúra. Itt szembetűnő különbség mutatkozik a véges világhoz képest: megmutatjuk, hogy véges testek feletti lineáris egyenletek megoldása már nehéz a Borel esetben. 

Másodszor, ha az idő engedi, arra térek ki, hogy a kompaktsági tétel különböző verzióinak egymáshoz képesti viszonya meglepő módon mégis tökéletesen tükrözi a Bulatov-Zhuk Dichotómiát, illetve arra, hogy miért gondolom azt, hogy ezek az ötletek használhatóak lehetnek a véges Dichotómia jobb megértésére is.

Back

JEvents v3.1.8 Stable   Copyright © 2006-2013