Description
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.