Leírás
Absztrakt: Egy A relációs struktúra feletti CSP (Constraint Satisfaction Problem) a következő eldöntési probléma. Adott egy primitív pozitív formula phi az A struktúra szignatúrájában, és eldöntendő, hogy phi igaz-e az A struktúrában. Bulatov és Zhuk híres eredménye szerint tudjuk, hogy amennyiben A véges, akkor CSP(A)-ra teljesül egy bonyolultságdichotómia: az összes ilyen probléma P-ben van vagy NP-teljes. Ezen eredményen felbuzdulva felmerül a kérdés, hogy az előbbi dichotómia mikor és hogyan általánosítható végtelen struktúrákra.
Az előadásomban ennek a problémának egy speciális esetéről fogok beszélni.
Tekintsük azt a színezett gráfot, amelynek csúcsai a természetes számok k elemű részhalmazai, és két csúcs olyan színű éllel van összekötve, mint ami a metszetük számossága. Az előadásomon során leírom ezen struktúráknak az elsőrendű reduktjait, és belátom, hogy az összes ilyen reduktnak a CSP-je vagy NP-nehéz vagy ekvivalens egy korábban vizsgált CSP-vel, amire már ismert a fenti bonyolultságdichotómia.
Az eredményből érdekes dolgok primitív pozitív definiálhatósága is következik, ezek közé tartozik például a 2023-as Schweitzer-verseny 7. feladatának állítása is.