Document Open Access Logo

Satisfiability of Circuits and Equations over Finite Malcev Algebras

Authors Paweł M. Idziak , Piotr Kawałek , Jacek Krzaczkowski

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.37.pdf
  • Filesize: 0.82 MB
  • 14 pages

Document Identifiers

Author Details

Paweł M. Idziak
  • Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
Piotr Kawałek
  • Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
Jacek Krzaczkowski
  • Department of Computer Science, Faculty of Mathematics, Physics and Computer Science, Maria Curie-Sklodowska University, Lublin, Poland

Funding

The project is partially supported by Polish NCN Grant # 2014/14/A/ST6/00138.
  • Kawałek, Piotr: This research is partially supported by the Priority Research Area SciMat under the program Excellence Initiative – Research University at the Jagiellonian University in Kraków.

Cite AsGet BibTex

Paweł M. Idziak, Piotr Kawałek, and Jacek Krzaczkowski. Satisfiability of Circuits and Equations over Finite Malcev Algebras. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.37

Abstract

We show that the satisfiability of circuits over finite Malcev algebra A is NP-complete or A is nilpotent. This strengthens the result from our earlier paper [Idziak and Krzaczkowski, 2018] where nilpotency has been enforced, however with the use of a stronger assumption that no homomorphic image of A has NP-complete circuits satisfiability. Our methods are moreover strong enough to extend our result of [Idziak et al., 2021] from groups to Malcev algebras. Namely we show that tractability of checking if an equation over such an algebra A has a solution enforces its nice structure: A must have a nilpotent congruence ν such that also the quotient algebra A/ν is nilpotent. Otherwise, if A has no such congruence ν then the Exponential Time Hypothesis yields a quasipolynomial lower bound. Both our results contain important steps towards a full characterization of finite algebras with tractable circuit satisfiability as well as equation satisfiability.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Complexity classes
Keywords
  • Circuit satisfiability
  • solving equations
  • Exponential Time Hypothesis

Metrics

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

References

  1. Erhard Aichinger and Nebojša Mudrinski. Some applications of higher commutators in Mal'cev algebras. Algebra Universalis, 63(4):367-403, 2010. URL: https://doi.org/10.1007/s00012-010-0084-1.
  2. David Mix Barrington, Pierre McKenzie, Cris Moore, Pascal Tesson, and Denis Thérien. Equation satisfiability and program satisfiability for finite monoids. In 25th International Symposium on Mathematical Foundations of Computer Science (MFCS 2000), pages 172-181. Springer Berlin Heidelberg, 2000. URL: https://doi.org/10.1007/3-540-44612-5_13.
  3. Stanley Burris and Hanamantagouda Sankappanavar. A Course in Universal Algebra With 36 Illustrations. Springer-Verlag, New York, 1981. Google Scholar
  4. Stephen Cook. The complexity of theorem proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC 1971), pages 151-158, 1971. URL: https://doi.org/10.1145/800157.805047.
  5. Attila Földvári and Gábor Horváth. The complexity of the equation solvability and equivalence problems over finite groups. International Journal of Algebra and Computation, 30(03):1-17, 2019. URL: https://doi.org/10.1142/S0218196720500137.
  6. Ralph Freese and Ralph McKenzie. Commutator Theory For Congruence Modular Varieties. London Mathematical Society Lecture Notes, No. 125. Cambridge University Press, 1987. Google Scholar
  7. Mikael Goldmann and Alexander Russell. The complexity of solving equations over finite groups. Information and Computation, 178(1):253-262, 2002. URL: https://doi.org/10.1006/inco.2002.3173.
  8. Tomasz Gorazd and Jacek Krzaczkowski. Term equation satisfiability over finite algebras. International Journal of Algebra and Computation, 20(08):1001-1020, 2010. URL: https://doi.org/10.1142/S021819671000600X.
  9. David Hobby and Ralph McKenzie. Structure of Finite Algebras. Contemporary Mathematics vol. 76. American Mathematical Society, 1988. URL: https://doi.org/10.1090/conm/076.
  10. 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.
  11. Gábor Horváth. The complexity of the equivalence and equation solvability problems over meta-abelian groups. Journal of Algebra, 433:208-230, 2015. URL: https://doi.org/10.1016/j.jalgebra.2015.03.015.
  12. Gábor Horváth and Csaba Szabó. The complexity of checking identities over finite groups. International Journal of Algebra and Computation, 16(05):931-940, 2006. URL: https://doi.org/10.1142/S0218196706003256.
  13. Gábor Horváth and Csaba Szabó. Equivalence and equation solvability problems for the alternating group A₄. Journal of Pure and Applied Algebra, 216(10):2170-2176, 2012. URL: https://doi.org/10.1016/j.jpaa.2012.02.007.
  14. Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski, and Armin Weiß. Equation satisfiability in solvable groups. To appear in Theory of Computing Systems, 2021. URL: http://arxiv.org/abs/2010.11788.
  15. Paweł Idziak, Piotr Kawałek, and Jacek Krzaczkowski. Expressive power, satisfiability and equivalence of circuits over nilpotent algebras. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117, pages 17:1-17:15. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.17.
  16. Paweł 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 2020), pages 578-590, 2020. URL: https://doi.org/10.1145/3373718.3394780.
  17. Paweł Idziak, Piotr Kawałek, and Jacek Krzaczkowski. Complexity of modular circuits, 2021. URL: http://arxiv.org/abs/2106.02947.
  18. Paweł Idziak and Jacek Krzaczkowski. Satisfiability in multi-valued circuits. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2018), pages 550-558, 2018. Full version: to appear in SIAM Journal on Computing (see also https://arxiv.org/1710.08163). URL: https://doi.org/10.1145/3209108.3209173.
  19. Piotr Kawałek, Michael Kompatscher, and Jacek Krzaczkowski. Circuit equivalence in 2-nilpotent algebras, 2019. URL: http://arxiv.org/abs/1909.12256.
  20. Keith Kearnes. Congruence modular varieties with small free spectra. Algebra Universalis, 42(3):165-181, 1999. URL: https://doi.org/10.1007/s000120050132.
  21. Ondrej Klíma. Complexity issues of checking identities in finite monoids. Semigroup Forum, 79(3):435-444, 2009. URL: https://doi.org/10.1007/s00233-009-9180-y.
  22. Michael Kompatscher. The equation solvability problem over supernilpotent algebras with mal’cev term. International Journal of Algebra and Computation, 28(06):1005-1015, 2018. URL: https://doi.org/10.1142/S0218196718500443.
  23. Michael Kompatscher. CSAT and CEQV for nilpotent Maltsev algebras of fitting length > 2, 2021. URL: http://arxiv.org/abs/2105.00689.
  24. Yuri Matiyasevich. Enumerable sets are diophantine. In Soviet Mathematics Doklady, volume 11, pages 354-358, 1970. Google Scholar
  25. Bernhard Schwarz. The complexity of satisfiability problems over finite lattices. In Annual Symposium on Theoretical Aspects of Computer Science (STACS 2004), pages 31-43. Springer Berlin Heidelberg, 2004. URL: https://doi.org/10.1007/978-3-540-24749-4_4.
  26. Armin Weiß. Hardness of equations over finite solvable groups under the exponential time hypothesis. In Proceedings of 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.102.
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