Document Open Access Logo

Knapsack Problems for Wreath Products

Authors Moses Ganardi, Daniel König, Markus Lohrey, Georg Zetzsche

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2018.32.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Subject Classification

Keywords
  • knapsack
  • wreath products
  • decision problems in group theory

Metrics

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

Abstract

In recent years, knapsack problems for (in general non-commutative) groups have attracted attention. In this paper, the knapsack problem for wreath products is studied. It turns out that decidability of knapsack is not preserved under wreath product. On the other hand, the class of knapsack-semilinear groups, where solutions sets of knapsack equations are effectively semilinear, is closed under wreath product. As a consequence, we obtain the decidability of knapsack for free solvable groups. Finally, it is shown that for every non-trivial abelian group G, knapsack (as well as the related subset sum problem)
for the wreath product G \wr Z is NP-complete.

Cite As Get BibTex

Moses Ganardi, Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack Problems for Wreath Products. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.32

Author Details

Moses Ganardi
Daniel König
Markus Lohrey
Georg Zetzsche

References

  1. T. C. Davis and A. Yu. Olshanskii. Subgroup distortion in wreath products of cyclic groups. Journal of Pure and Applied Algebra, 215(12):2987-3004, 2011. Google Scholar
  2. M. Elberfeld, A. Jakoby, and T. Tantau. Algorithmic meta theorems for circuit classes of constant and logarithmic depth. Electronic Colloquium on Computational Complexity (ECCC), 18:128, 2011. Google Scholar
  3. E. Frenkel, A. Nikolaev, and A. Ushakov. Knapsack problems in products of groups. Journal of Symbolic Computation, 74:96-108, 2016. Google Scholar
  4. M. Ganardi, D. König, M. Lohrey, and G. Zetzsche. Knapsack problems for wreath products. CoRR, abs/1709.09598, 2017. URL: http://arxiv.org/abs/1709.09598.
  5. S. Ginsburg and E. H. Spanier. Semigroups, Presburger formulas, and languages. Pacific Journal of Mathematics, 16(2):285-296, 1966. URL: http://dx.doi.org/10.2140/pjm.1966.16.285.
  6. C. Haase. On the complexity of model checking counter automata. PhD thesis, University of Oxford, St Catherine’s College, 2011. Google Scholar
  7. R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972. Google Scholar
  8. D. König, M. Lohrey, and G. 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
  9. J. Lehnert and P. Schweitzer. The co-word problem for the Higman-Thompson group is context-free. Bulletin of the London Mathematical Society, 39(2):235-241, 2007. Google Scholar
  10. M. Lohrey, B. Steinberg, and G. Zetzsche. Rational subsets and submonoids of wreath products. Information and Computation, 243:191-204, 2015. Google Scholar
  11. M. Lohrey and G. Zetzsche. Knapsack in graph groups, HNN-extensions and amalgamated products. In Nicolas Ollinger and Heribert Vollmer, editors, Proc. of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016), volume 47 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1-50:14, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  12. M. Lohrey and G. Zetzsche. The complexity of knapsack in graph groups. In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, volume 66 of LIPIcs, pages 52:1-52:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  13. A. Miasnikov, S. Vassileva, and A. Weiß. The conjugacy problem in free solvable groups and wreath products of abelian groups is in TC⁰. In Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings, volume 10304 of Lecture Notes in Computer Science, pages 217-231. Springer, 2017. Google Scholar
  14. A. Mishchenko and A. Treier. Knapsack problem for nilpotent groups. Groups Complexity Cryptology, 9(1):87-98, 2017. Google Scholar
  15. A. Myasnikov, A. Nikolaev, and A. Ushakov. Knapsack problems in groups. Mathematics of Computation, 84:987-1016, 2015. Google Scholar
  16. A. Nikolaev and A. Ushakov. Subset sum problem in polycyclic groups. Journal of Symbolic Computation, 84:84-94, 2018. Google Scholar
  17. C. Sims. Computation with finitely presented groups. Cambridge University Press, 1994. Google Scholar
  18. M. Wilhelm. On a theorem of Marshall Hall. Annals of Mathematics. Second Series, 40:764-768, 1939. 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