2026-07-25T02:34:12Z
https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:18600
2024-03-06T11:02:14Z
ddc:004
open_access
On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras
Mayr, Peter
systems of equations
general algebras
constraint satisfaction
For a fixed finite algebra π, we consider the decision problem SysTerm(π): does a given system of term equations have a solution in π? This is equivalent to a constraint satisfaction problem (CSP) for a relational structure whose relations are the graphs of the basic operations of π. From the complexity dichotomy for CSP over fixed finite templates due to Bulatov [Bulatov, 2017] and Zhuk [Zhuk, 2017], it follows that SysTerm(π) for a finite algebra π is in P if π has a not necessarily idempotent Taylor polymorphism and is NP-complete otherwise. More explicitly, we show that for a finite algebra π in a congruence modular variety (e.g. for a quasigroup), SysTerm(π) is in P if the core of π is abelian and is NP-complete otherwise. Given π by the graphs of its basic operations, we show that this condition for tractability can be decided in quasi-polynomial time.
Schloss Dagstuhl β Leibniz-Zentrum fΓΌr Informatik
Peter Mayr
2023
Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
InProceedings
Text
doc-type:ResearchArticle
publishedVersion
application/pdf
doi:10.4230/LIPIcs.MFCS.2023.66
urn:nbn:de:0030-drops-186007
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.66
eng
https://creativecommons.org/licenses/by/4.0/legalcode