Conservative Maltsev Constraint Satisfaction Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910014898176000 |
|---|---|
| author | Bodirsky, Manuel Moorhead, Andrew |
| author_facet | Bodirsky, Manuel Moorhead, Andrew |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_11395 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Conservative Maltsev Constraint Satisfaction Problems Bodirsky, Manuel Moorhead, Andrew Rings and Algebras Computational Complexity 68W99 (primary), 08A05 (secondary), 08A62 (secondary) F.1.3 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. |
| title | Conservative Maltsev Constraint Satisfaction Problems |
| topic | Rings and Algebras Computational Complexity 68W99 (primary), 08A05 (secondary), 08A62 (secondary) F.1.3 |
| url | https://arxiv.org/abs/2505.11395 |