LIPIcs.MFCS.2023.66.pdf
- Filesize: 0.64 MB
- 12 pages
Document
On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras
Author
-
Part of:
Volume:
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-08-21
File
Document Identifiers
Acknowledgements
I want to thank E. Aichinger for discussions on this problem and the referees for their diligent reading and comments.
Cite As Get BibTex
Peter Mayr. On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 66:1-66:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.MFCS.2023.66
Abstract
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Problems, reductions and completeness
Keywords
- systems of equations
- general algebras
- constraint satisfaction
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- L. Barto, A. Krokhin, and R. Willard. Polymorphisms, and how to use them. In Andrei A. Krokhin and Stanislav Zivný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.1.
-
C. Bergman. Universal algebra, volume 301 of Pure and Applied Mathematics (Boca Raton). CRC Press, Boca Raton, FL, 2012. Fundamentals and selected topics.
- P. Broniek. Computational complexity of solving equation systems. SpringerBriefs in Philosophy. Springer, Cham, 2015. URL: https://doi.org/10.1007/978-3-319-21750-5.
- A. Bulatov. A dichotomy theorem for nonuniform CSPs. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319-330. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
-
S. Burris and H. P. Sankappanavar. A course in universal algebra. Springer New York Heidelberg Berlin, 1981.
- H. Chen and B. Larose. Asking the metaquestions in constraint tractability. ACM Trans. Comput. Theory, 9(3):Art. 11, 27, 2017. URL: https://doi.org/10.1145/3134757.
- W. DeMeo, R. Freese, and M. Valeriote. Polynomial-time tests for difference terms in idempotent varieties. Internat. J. Algebra Comput., 29(6):927-949, 2019. URL: https://doi.org/10.1142/S021819671950036X.
- T. Feder and M. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput., 28(1):57-104 (electronic), 1999. URL: https://doi.org/10.1137/S0097539794266766.
-
R. Freese and R. N. McKenzie. Commutator Theory for Congruence Modular Varieties, volume 125 of London Math. Soc. Lecture Note Ser. Cambridge University Press, 1987. Available from ěrb+http://math.hawaii.edu/ ralph/Commutator/comm.pdf+.
- R. Freese and M. A. Valeriote. On the complexity of some Maltsev conditions. Internat. J. Algebra Comput., 19(1):41-77, 2009. URL: https://doi.org/10.1142/S0218196709004956.
- M. Goldmann and A. Russell. The complexity of solving equations over finite groups. Inf. Comput., 178(1):253-262, 2002. URL: https://doi.org/10.1006/inco.2002.3173.
-
D. Hobby and R. McKenzie. The structure of finite algebras, volume 76 of Contemporary mathematics. American Mathematical Society, 1988.
- K. Kearnes, P. Marković, and R. McKenzie. Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties. Algebra Universalis, 72(1):91-100, 2014. URL: https://doi.org/10.1007/s00012-014-0289-9.
- O. Klíma, P. Tesson, and D. Thérien. Dichotomies in the complexity of solving systems of equations over finite semigroups. Theory Comput. Syst., 40(3):263-297, 2007. URL: https://doi.org/10.1007/s00224-005-1279-2.
- B. Larose and L. Zádori. Taylor terms, constraint satisfaction and the complexity of polynomial equations over finite algebras. Internat. J. Algebra Comput., 16(3):563-581, 2006. URL: https://doi.org/10.1142/S0218196706003116.
-
R. N. McKenzie, G. F. McNulty, and W. F. Taylor. Algebras, lattices, varieties, Volume I. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, California, 1987.
- M. Siggers. A strong Mal'cev condition for locally finite varieties omitting the unary type. Algebra Universalis, 64(1-2):15-20, 2010. URL: https://doi.org/10.1007/s00012-010-0082-3.
- D. Zhuk. A proof of CSP dichotomy conjecture. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 331-342. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.38.