Document Open Access Logo

Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras

Authors Pawel M. Idziak, Piotr Kawalek, Jacek Krzaczkowski

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.17.pdf
  • Filesize: 491 kB
  • 15 pages

Document Identifiers

Author Details

Pawel M. Idziak
  • Jagiellonian University, Faculty of Mathematics and Computer Science, Department of Theoretical Computer Science, Krakow, Poland
Piotr Kawalek
  • Jagiellonian University, Faculty of Mathematics and Computer Science, Department of Theoretical Computer Science, Krakow, Poland
Jacek Krzaczkowski
  • Jagiellonian University, Faculty of Mathematics and Computer Science, Department of Theoretical Computer Science, Krakow, Poland

Funding

The project is partially supported by Polish NCN Grant # 2014/14/A/ST6/00138.

Cite As Get BibTex

Pawel M. Idziak, Piotr Kawalek, 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.17

Abstract

Satisfiability of Boolean circuits is NP-complete in general but becomes polynomial time when restricted for example either to monotone gates or linear gates. We go outside Boolean realm and consider circuits built of any fixed set of gates on an arbitrary large finite domain. From the complexity point of view this is connected with solving equations over finite algebras. This in turn is one of the oldest and well-known mathematical problems which for centuries was the driving force of research in algebra. Let us only mention Galois theory, Gaussian elimination or Diophantine Equations. The last problem has been shown to be undecidable, however in finite realms such problems are obviously decidable in nondeterministic polynomial time.
A project of characterizing finite algebras m A with polynomial time algorithms deciding satisfiability of circuits over m A has been undertaken in [Pawel M. Idziak and Jacek Krzaczkowski, 2018]. Unfortunately that paper leaves a gap for nilpotent but not supernilpotent algebras. In this paper we discuss possible attacks on filling this gap.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Circuit complexity
  • Theory of computation → Constraint and logic programming
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • circuit satisfiability
  • solving equations
  • Constraint Satisfaction Problem
  • structure theory

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. Google Scholar
  2. A. A. Bulatov. A dichotomy theorem for nonuniform CSPs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 319-330, Oct. 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.37.
  3. Andrei Bulatov. On the number of finite Mal’tsev algebras. Contributions to General Algebra, 13:41-54, 2000. Google Scholar
  4. Stanley Burris and H. P. Sankappanavar. A course in universal algebra, volume 78 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1981. Google Scholar
  5. Tomás Feder, Florent Madelaine, and Iain A. Stewart. Dichotomies for classes of homomorphism problems involving unary functions. Theoret. Comput. Sci., 314(1-2):1-43, 2004. Google Scholar
  6. Ralph Freese and Ralph McKenzie. Commutator theory for congruence modular varieties, volume 125 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1987. Google Scholar
  7. Mikael Goldmann and Alexander Russell. The complexity of solving equations over finite groups. Inform. and Comput., 178(1):253-262, 2002. Google Scholar
  8. 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. Google Scholar
  9. Gábor Horváth. The complexity of the equivalence and equation solvability problems over meta-Abelian groups. Journal of Algebra, 433:208-230, 2015. Google Scholar
  10. Gábor Horváth and Csaba Szabó. The Complexity of Checking Identities over Finite Groups. Internat. J. Algebra Comput., 16(5):931-940, 2006. URL: http://dx.doi.org/10.1142/S0218196706003256.
  11. 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. Google Scholar
  12. Paweł M. Idziak and Jacek Krzaczkowski. Satisfiability in multi-valued circuits. In 2018 Thirty-Third Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2018. Google Scholar
  13. K.A. Kearnes. Congruence modular varieties with small free spectra. Algebra Universalis, 42(3):165–181, Oct 1999. URL: http://dx.doi.org/10.1007/s000120050132.
  14. Michael Kompatscher. The equation solvability problem over nilpotent mal'cev algebras. arXiv, 2017. URL: http://arxiv.org/abs/1710.03083.
  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. Google Scholar
  16. Jiyou Li and Daqing Wan. On the subset sum problem over finite fields. Finite Fields and Their Applications, 14(4):911–929, 2008. URL: http://dx.doi.org/10.1016/j.ffa.2008.05.003.
  17. Ju. V. Matijasevič. The Diophantineness of enumerable sets. Dokl. Akad. Nauk SSSR, 191:279-282, 1970. Google Scholar
  18. Christos H. Papadimitriou. Computational complexity. Addison-Wesley Publishing Company, Reading, MA, 1994. Google Scholar
  19. Bernhard Schwarz. The Complexity of Satisfiability Problems over Finite Lattices. In 2004 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS), page 31–43, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Google Scholar
  20. D. Zhuk. A proof of CSP dichotomy conjecture. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 331-342, Oct. 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.38.
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 About DROPS Imprint Privacy Contact