Document Open Access Logo

The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term

Authors Erhard Aichinger , Simon Grünbacher

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.4.pdf
  • Filesize: 0.76 MB
  • 12 pages

Document Identifiers

Author Details

Erhard Aichinger
  • Institute for Algebra, Johannes Kepler Universität Linz, Austria
Simon Grünbacher
  • Institute for Algebra, Johannes Kepler Universität Linz, Austria

Funding

Supported by the Austrian Science Fund FWF P33878: Equations in Universal Algebra.

Acknowledgements

The authors thank M. Behrisch for discussions on this problem, the referees of a previous version for their criticism that helped to improve the result, and the referees of the present version for several suggestions improving the presentation.

Cite AsGet BibTex

Erhard Aichinger and Simon Grünbacher. The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.4

Abstract

We consider finite algebraic structures and ask whether every solution of a given system of equations satisfies some other equation. This can be formulated as checking the validity of certain first order formulae called quasi-identities. Checking the validity of quasi-identities is closely linked to solving systems of equations. For systems of equations over finite algebras with finitely many fundamental operations, a complete P/NPC dichotomy is known, while the situation appears to be more complicated for single equations. The complexity of checking the validity of a quasi-identity lies between the complexity of term equivalence (checking whether two terms induce the same function) and the complexity of solving systems of polynomial equations. We prove that for each finite algebra with a Mal'cev term and finitely many fundamental operations, checking the validity of quasi-identities is coNP-complete if the algebra is not abelian, and in P when the algebra is abelian.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
  • Theory of computation → Complexity classes
Keywords
  • quasi-identities
  • conditional identities
  • systems of equations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Erhard Aichinger. The polynomial functions of certain algebras that are simple modulo their center. In Contributions to general algebra. 17, pages 9-24. Heyn, Klagenfurt, 2006. Google Scholar
  2. Erhard Aichinger, Nebojša Mudrinski, and Jakub Opršal. Complexity of term representations of finitary functions. Internat. J. Algebra Comput., 28(6):1101-1118, 2018. URL: https://doi.org/10.1142/S0218196718500480.
  3. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 319-330, 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  4. Stanley Burris and John Lawrence. The equivalence problem for finite rings. J. Symbolic Comput., 15(1):67-71, 1993. URL: https://doi.org/10.1142/S021819671100625X.
  5. Stanley Burris and Hanamantagouda P. Sankappanavar. A course in universal algebra. Springer New York Heidelberg Berlin, 1981. Google Scholar
  6. Pete L. Clark. The Combinatorial Nullstellensätze revisited. Electron. J. Combin., 21(4):Paper 4.15, 17, 2014. URL: https://doi.org/10.37236/4359.
  7. Tomás Feder and Moshe Y. 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.
  8. Ralph Freese and Ralph N. McKenzie. Commutator Theory for Congruence Modular varieties, volume 125 of London Math. Soc. Lecture Note Ser. Cambridge University Press, 1987. Google Scholar
  9. Mikael Goldmann and Alexander Russell. The complexity of solving equations over finite groups. Inform. and Comput., 178(1):253-262, 2002. URL: https://doi.org/10.1006/inco.2002.3173.
  10. Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. J. Combin. Theory Ser. B, 48(1):92-110, 1990. URL: https://doi.org/10.1016/0095-8956(90)90132-J.
  11. David Hobby and Ralph N. McKenzie. The structure of finite algebras, volume 76 of Contemporary Mathematics. American Mathematical Society, Providence, RI, 1988. URL: https://doi.org/10.1090/conm/076.
  12. Gábor Horváth. The complexity of the equivalence and equation solvability problems over nilpotent rings and groups. Algebra universalis, 66(4):391-403, 2011. URL: https://doi.org/10.1007/s00012-011-0163-y.
  13. Gábor Horváth and Csaba Szabó. The extended equivalence and equation solvability problems for groups. Discrete Mathematics & Theoretical Computer Science, Vol. 13 no. 4, 2011. URL: https://doi.org/10.46298/dmtcs.536.
  14. Paweł M. Idziak, Piotr Kawałek, and Jacek Krzaczkowski. Intermediate problems in modular circuits satisfiability. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '20, pages 578-590. Association for Computing Machinery, 2020. URL: https://doi.org/10.1145/3373718.3394780.
  15. Benoit Larose and László 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.
  16. Anatoly I. Mal'cev. On the general theory of algebraic systems. Mat. Sb. N.S., 35(77):3-20, 1954. Google Scholar
  17. Ralph N. McKenzie, George F. McNulty, and Walter F. Taylor. Algebras, lattices, varieties, Volume I. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, California, 1987. Google Scholar
  18. Michael Sipser. Introduction to the Theory of Computation. Cengage Learning, Boston, MA, USA, 3rd edition, 2012. URL: https://books.google.at/books?id=1aMKAAAAQBAJ.
  19. Guy Terjanian. Sur les corps finis. C. R. Acad. Sci. Paris Sér. A-B, 262:A167-A169, 1966. Google Scholar
  20. Mikhail V. Volkov. Checking quasi-identities in a finite semigroup may be computationally hard. Studia Logica, 78(1-2):349-356, 2004. URL: https://doi.org/10.1007/s11225-005-0356-5.
  21. Armin Weiß. Hardness of equations over finite solvable groups under the exponential time hypothesis. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 102:1-102:19, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.102.
  22. László Zádori. Solvability of systems of polynomial equations over finite algebras. Internat. J. Algebra Comput., 17(4):821-835, 2007. URL: https://doi.org/10.1142/S0218196707003809.
  23. Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. Journal of the ACM, 67(5):1-78, 2020. URL: https://doi.org/10.1145/3402029.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact