Constraint satisfaction problems: algebraický prístup ku klasifikácii výpočtovej zložitosti
Prednášajúca: Žaneta Semanišinová / Inštitút algebry, Technická univerzita v Drážďanoch, Nemecko
Kedy: 8. február 2024, od 11:00-12:00 h
Kde: SJ2P11, Jesenná 5, Košice
Abstrakt:
Problém splniteľnosti obmedzujúcich podmienok (CSP – Constraint satisfaction problem) poskytuje spoločný rámec pre štúdium množstva prirodzených výpočtových problémov z rôznych oblastí matematiky a informatiky, napríklad Problém splniteľnosti logických formúl, Problém ofarbiteľnosti grafu alebo rôzne rozvrhovacie problémy. V mnohých prípadoch existujú efektívne algoritmy na riešenie týchto problémov (v polynomiálnom čase), v iných vieme dokázať, že sú NP-ťažké a predpokladáme, že žiadny efektívny algoritmus na ich riešenie neexistuje. Pre fixnú relačnú štruktúru B, CSP(B) je problém, ktorého vstupom je konečná relačná štruktúra A a výstupom je odpoveď na otázku, či existuje homomorfizmus z A do B. V prednáške sa zameriame na algebraický prístup ku klasifikácii zložitosti CSP a na výsledky týkajúce sa CSP na konečných a nekonečných množinách. V závere sa pozrieme na optimalizačný variant CSP, tzv. Valued constraint satisfaction problem.
