Document Open Access Logo

Satisfiability Problems for Finite Groups

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.127.pdf
  • Filesize: 0.89 MB
  • 20 pages

Document Identifiers

Author Details

Paweł M. Idziak
  • Jagiellonian University, Kraków, Poland
Piotr Kawałek
  • Jagiellonian University, Kraków, Poland
Jacek Krzaczkowski
  • Maria Curie-Sklodowska University, Lublin, Poland
Armin Weiß
  • Universität Stuttgart, FMI, Germany

Funding

This research is partially supported by Polish NCN Grant # 2014/14/A/ST6/00138 and German DFG Grant WE 6835/1-2.

Cite As Get BibTex

Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, and Armin Weiß. Satisfiability Problems for Finite Groups. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 127:1-127:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.127

Abstract

Over twenty years ago, Goldmann and Russell initiated the study of the complexity of the equation satisfiability problem (PolSat and the NUDFA program satisfiability problem (ProgramSat) in finite groups. They showed that these problems are in 𝖯 for nilpotent groups while they are NP-complete for non-solvable groups.
In this work we completely characterize finite groups for which the problem ProgramSat can be solved in randomized polynomial time under the assumptions of the Randomized Exponential Time Hypothesis and the Constant Degree Hypothesis. We also determine the complexity of PolSat for a wide class of finite groups. As a by-product, we obtain a classification for ListPolSat, a version of PolSat where each variable can be restricted to an arbitrary subset. Finally, we also prove unconditional algorithms for these problems in certain cases.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Complexity classes
Keywords
  • Satisifiability
  • Solvable groups
  • ProgramSat
  • PolSat
  • Exponential Time Hypothesis

Metrics

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

References

  1. David A. Mix Barrington. Width-3 permutation branching programs. Technical Report TM-293, MIT Laboratory for Computer Science, 1985. Google Scholar
  2. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹. In Proceedings of STOC'86, pages 1-5, 1986. URL: https://doi.org/10.1145/12130.12131.
  3. David A. Mix Barrington, Richard Beigel, and Steven Rudich. Representing Boolean functions as polynomials modulo composite numbers. Computational Complexity, 4:367-382, 1994. URL: https://doi.org/10.1007/BF01263424.
  4. David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, and Denis Thérien. Equation satisfiability and program satisfiability for finite monoids. In Proceedings of MFCS'00, pages 172-181, 2000. URL: https://doi.org/10.1007/3-540-44612-5_13.
  5. David A. Mix Barrington, Howard Straubing, and Denis Thérien. Non-uniform automata over groups. Inf. Comput., 89(2):109-132, 1990. URL: https://doi.org/10.1016/0890-5401(90)90007-5.
  6. David A. Mix Barrington and Denis Thérien. Finite monoids and the fine structure of NC^1. J. ACM, 35(4):941-952, 1988. URL: https://doi.org/10.1145/48014.63138.
  7. Gil Cohen and Avishay Tal. Two structural results for low degree polynomials and applications. In Proceedings of APPROX/RANDOM'15, pages 680-709, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.680.
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  9. Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlen. Exponential time complexity of the permanent and the Tutte polynomial. ACM Trans. Algorithms, 10(4):21:1-21:32, 2014. URL: https://doi.org/10.1145/2635812.
  10. Volker Diekert, Claudio Gutiérrez, and Christian Hagenah. The existential theory of equations with rational constraints in free groups is PSPACE-complete. Inf. Comput., 202(2):105-140, 2005. URL: https://doi.org/10.1016/j.ic.2005.04.002.
  11. Attila Földvári. The complexity of the equation solvability problem over semipattern groups. IJAC, 27(2):259, 2017. URL: https://doi.org/10.1142/S0218196717500126.
  12. Attila Földvári and Gábor Horváth. The complexity of the equation solvability and equivalence problems over finite groups. IJAC, 30(03):607-623, 2020. URL: https://doi.org/10.1142/S0218196720500137.
  13. Ralph Freese and Ralph McKenzie. Commutator Theory for Congruence Modular Varieties. London Mathematical Society Lecture Notes, No. 125. Cambridge University Press, 1987. Google Scholar
  14. Mikael Goldmann and Alexander 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.
  15. Vince Grolmusz. A degree-decreasing lemma for (MOD_p-MOD_m) circuits. Discret. Math. Theor. Comput. Sci., 4(2):247-254, 2001. URL: https://doi.org/10.46298/dmtcs.289.
  16. Vince Grolmusz and Gábor Tardos. Lower bounds for (MOD_p-MOD_m) circuits. SIAM J. Comput., 29(4):1209-1222, 2000. URL: https://doi.org/10.1137/S0097539798340850.
  17. 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.
  18. Gábor Horváth. The complexity of the equivalence and equation solvability problems over meta-Abelian groups. J. Algebra, 433:208-230, 2015. URL: https://doi.org/10.1016/j.jalgebra.2015.03.015.
  19. Gábor Horváth and Csaba A. Szabó. The complexity of checking identities over finite groups. IJAC, 16(5):931-940, 2006. URL: https://doi.org/10.1142/S0218196706003256.
  20. Paweł M. Idziak, Piotr Kawałek, and Jacek Krzaczkowski. Intermediate problems in modular circuits satisfiability. In Proceedings of LICS'20, pages 578-590, 2020. URL: https://doi.org/10.1145/3373718.3394780.
  21. Pawel M. Idziak, Piotr Kawalek, and Jacek Krzaczkowski. Complexity of modular circuits. In 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (LICS ’22), August 2–5, 2022, Haifa, Israel. ACM, New York, NY, USA, 2022. URL: https://doi.org/10.1145/3531130.3533350.
  22. Pawel M. Idziak, Piotr Kawalek, and Jacek Krzaczkowski. Satisfiability of circuits and equations over finite Malcev algebras. In Proceedings of STACS'22, pages 37:1-37:14, 2022. URL: https://doi.org/10.4230/LIPIcs.STACS.2022.37.
  23. Pawel M. Idziak, Piotr Kawalek, Jacek Krzaczkowski, and Armin Weiß. Equation satisfiability in solvable groups. Theory Comput. Syst., to appear, 2022. URL: http://arxiv.org/abs/2010.11788.
  24. Paweł M. Idziak and Jacek Krzaczkowski. Satisfiability in multi-valued circuits. SIAM J. Comp., 51(3):337-378, 2022. URL: https://doi.org/10.1137/18M1220194.
  25. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  26. J. D. P. Meldrum. Wreath products of groups and semigroups, volume 74 of Pitman Monographs and Surveys in Pure and Applied Mathematics. Longman, Harlow, 1995. Google Scholar
  27. Christos H. Papadimitriou. Computational Complexity. Addison Wesley, 1994. Google Scholar
  28. Derek J. S. Robinson. A course in the theory of groups, volume 80 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1996. URL: https://doi.org/10.1007/978-1-4419-8594-1.
  29. Klaus U. Schulz. Makanin’s algorithm for word equations - two improvements and a generalization. In Proceedings of Word Equations and Related Topics, First International Workshop, IWWERT, pages 85-150, 1990. URL: https://doi.org/10.1007/3-540-55124-7_4.
  30. Armin Weiß. Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis. In Proceedings of ICALP'20, pages 102:1-102:19, 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 About DROPS Imprint Privacy Contact