Document Open Access Logo

Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups

Authors Markus Lohrey , Georg Zetzsche

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2020.67.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • computational group theory
  • matrix problems
  • Baumslag-Solitar groups

Metrics

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

Abstract

We prove that the power word problem for the solvable Baumslag-Solitar groups BS(1,q) = ⟨ a,t ∣ t a t^{-1} = a^q ⟩ can be solved in TC⁰. In the power word problem, the input consists of group elements g₁, …, g_d and binary encoded integers n₁, …, n_d and it is asked whether g₁^{n₁} ⋯ g_d^{n_d} = 1 holds. Moreover, we prove that the knapsack problem for BS(1,q) is NP-complete. In the knapsack problem, the input consists of group elements g₁, …, g_d,h and it is asked whether the equation g₁^{x₁} ⋯ g_d^{x_d} = h has a solution in ℕ^d.

Cite As Get BibTex

Markus Lohrey and Georg Zetzsche. Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 67:1-67:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.MFCS.2020.67

Author Details

Markus Lohrey
  • Universität Siegen, Germany
Georg Zetzsche
  • Max Planck Institute for Software Systems (MPI-SWS), Kaiserslautern, Germany

Funding

  • Lohrey, Markus: Funded by DFG project LO 748/12-1.

References

  1. Eric Allender, Nikhil Balaji, and Samir Datta. Low-depth uniform threshold circuits and the bit-complexity of straight line programs. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science 2014, MFCS 2014, volume 8635 of Lecture Notes in Computer Science, pages 13-24. Springer, 2014. Google Scholar
  2. Lázló Babai, Robert Beals, Jin yi Cai, Gábor Ivanyos, and Eugene M.Luks. Multiplicative equations over commuting matrices. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996, pages 498-507. ACM/SIAM, 1996. Google Scholar
  3. Laurent Bartholdi, Michael Figelius, Markus Lohrey, and Armin Weiß. Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems. CoRR, abs/1909.13781, 2019. URL: https://arxiv.org/abs/1909.13781.
  4. Gilbert Baumslag. Wreath products and finitely presented groups. Mathematische Zeitschrift, 75(1):22-28, 1961. Google Scholar
  5. Véronique Bruyère. Entiers et automates finis. Mémoire de fin d'études, Université de Mons, 1985. Google Scholar
  6. Véronique Bruyère, Georges Hansel, Christian Michaux, and Roger Villemaire. Logic and p-recognizable sets of integers. Bulletin of the Belgian Mathematical Society, 1:191-238, 1994. Google Scholar
  7. J Richard Büchi. Weak second-order arithmetic and finite automata. Mathematical Logic Quarterly, 6(1-6):66-92, 1960. Google Scholar
  8. Jin-Yi Cai, Richard J. Lipton, and Yechezkel Zalcstein. The complexity of the A B C problem. SIAM Journal on Computing, 29(6):1878-1888, 2000. Google Scholar
  9. Fedor Dudkin and Alexander Treyer. Knapsack problem for Baumslag-Solitar groups. Siberian Journal of Pure and Applied Mathematics, 18:43-55, 2018. Google Scholar
  10. Wayne Eberly. Very fast parallel polynomial arithmetic. SIAM Journal on Computing, 18(5):955-976, 1989. Google Scholar
  11. Michael Figelius, Moses Ganardi, Markus Lohrey, and Georg Zetzsche. The complexity of knapsack problems in wreath products. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, volume 168 of LIPIcs, pages 126:1-126:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  12. Michael Figelius, Markus Lohrey, and Georg Zetzsche. Closure properties of knapsack semilinear groups. CoRR, abs/1911.12857, 2019. URL: https://arxiv.org/abs/1911.12857.
  13. Elizaveta Frenkel, Andrey Nikolaev, and Alexander Ushakov. Knapsack problems in products of groups. Journal of Symbolic Computation, 74:96-108, 2016. Google Scholar
  14. Esther Galby, Joël Ouaknine, and James Worrell. On matrix powering in low dimensions. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, volume 30 of LIPIcs, pages 329-340. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. Google Scholar
  15. Moses Ganardi, Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack problems for wreath products. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, volume 96 of LIPIcs, pages 32:1-32:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  16. Guoqiang Ge. Testing equalities of multiplicative representations in polynomial time (extended abstract). In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, FOCS 1993, pages 422-426. IEEE Computer Society, 1993. Google Scholar
  17. Florent Guépin, Christoph Haase, and James Worrell. On the existential theories of Büchi arithmetic and linear p-adic fields. In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, pages 1-10. IEEE Computer Society, 2019. Google Scholar
  18. Christoph Haase. On the complexity of model checking counter automata. PhD thesis, University of Oxford, St Catherine’s College, 2011. Google Scholar
  19. William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences, 65(4):695-716, 2002. Google Scholar
  20. Christopher Hooley. On Artin’s conjecture. Journal für die reine und angewandte Mathematik, 1967(225):209-220, 1967. Google Scholar
  21. Olga Kharlampovich, Laura López, and Alexei Myasnikov. The diophantine problem in some metabelian groups. Mathematics of Computation, 89:2507-2519, 2020. Google Scholar
  22. Daniel König and Markus Lohrey. Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica, 80(5):1459-1492, 2018. Google Scholar
  23. Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups. In Algebra and Computer Science, volume 677 of Contemporary Mathematics, pages 138-153. American Mathematical Society, 2016. Google Scholar
  24. Klaus-Jörn Lange and Pierre McKenzie. On the complexity of free monoid morphisms. In Proceedings of the 9th International Symposium on Algorithms and Computation, ISAAC 1998, number 1533 in Lecture Notes in Computer Science, pages 247-256. Springer, 1998. Google Scholar
  25. Markus Lohrey. The Compressed Word Problem for Groups. SpringerBriefs in Mathematics. Springer, 2014. Google Scholar
  26. Markus Lohrey. Knapsack in hyperbolic groups. Journal of Algebra, 545:390-415, 2020. Google Scholar
  27. Markus Lohrey and Armin Weiß. The power word problem. In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, volume 138 of LIPIcs, pages 43:1-43:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  28. Markus Lohrey and Armin Weiß. The power word problem. CoRR, abs/1904.08343, 2019. URL: http://arxiv.org/abs/1904.08343.
  29. Markus Lohrey and Georg Zetzsche. Knapsack in graph groups. Theory of Computing Systems, 62(1):192-246, 2018. Google Scholar
  30. Markus Lohrey and Georg Zetzsche. Knapsack and the power word problem in solvable Baumslag-Solitar groups. CoRR, abs/2002.03837, 2020. URL: https://arxiv.org/abs/2002.03837.
  31. Alexei Miasnikov, Vitaly Roman'kov, Alexander Ushakov, and Anatoly Vershik. The word and geodesic problems in free solvable groups. Transactions of the American Mathematical Society, 362(9):4655-4682, 2010. Google Scholar
  32. Alexei Mishchenko and Alexander Treier. Knapsack problem for nilpotent groups. Groups Complexity Cryptology, 9(1):87, 2017. Google Scholar
  33. Alexei Myasnikov, Andrey Nikolaev, and Alexander Ushakov. Knapsack problems in groups. Mathematics of Computation, 84:987-1016, 2015. Google Scholar
  34. Melvyn B. Nathanson. Elementary Methods in Number Theory. Springer, 2000. Google Scholar
  35. David Robinson. Parallel Algorithms for Group Word Problems. PhD thesis, University of California, San Diego, 1993. Google Scholar
  36. Heribert Vollmer. Introduction to Circuit Complexity. Springer, 1999. Google Scholar
  37. Armin Weiß. On the complexity of conjugacy in amalgamated products and HNN extensions. PhD thesis, University of Stuttgart, 2015. URL: http://elib.uni-stuttgart.de/opus/volltexte/2015/10018/.
  38. Armin Weiß. A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups. CoRR, abs/1602.02445, 2016. URL: https://arxiv.org/abs/1602.02445.
  39. Wolfgang Woess. Random Walks on Infinite Graphs and Groups. Cambridge University Press, 2000. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact