3 papers
cs.CC2026
Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
Leonid Dorochko, MichaÅ Wrona
Feder-Vardi conjecture, which proposed that every finite-domain Constraint Satisfaction Problem (CSP) is either in P or it is NP-complete, has been solved independently by Bulatov…
cs.LO2024
Model-checking positive equality free logic on a fixed structure (direttissima)
Manuel Bodirsky, Marcin Kozik, Florent Madelaine +2
We give a new, direct proof of the tetrachotomy classification for the model-checking problem of positive equality-free logic parameterised by the model. The four complexity classe…
cs.LO2024
Quasi Directed Jonsson Operations Imply Bounded Width (For fo-expansions of symmetric binary cores with free amalgamation)
Michal Wrona
Every CSP(B) for a finite structure B is either in P or it is NP-complete but the proofs of the finite-domain CSP dichotomy by Andrei Bulatov and Dimitryi Zhuk not only show the co…