2025/05/16 by Manuel Bodirsky, Bodirsky, Manuel, Andrew Moorhead +1 · 1 citation
Computer Science · #08A05 (secondary) #08A62 (secondary) #68W99 (primary) #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #F.1.3 #FOS: Computer and information sciences #FOS: Mathematics #Rings and Algebras (math.RA)
paper · pdf · doi:10.48550/arxiv.2505.11395
openalex publication_date 2025/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One of the central open problems to classify the computational complexity of finite-domain constraint satisfaction problems within P is to prove better algorithmic results for CSPs with a Maltsev polymorphism; we do not even know whether these CSPs are in NC. Relatedly, the descriptive complexity of these problems is open as well. An important special case, previously studied by Carbonell from the perspective of uniform polynomial time-algorithms, are CSPs with a conservative Maltsev polymorphism. We show that for every finite structure B with a conservative Maltsev polymorphism, the CSP for B can be solved by a symmetric linear Z2-Datalog program, and in particular is in the complexity class parity-L. Previously, the best known algorithms just showed containment in P. In our proof we develop a structure theory for conservative Maltsev algebras which might be of independent interest.