License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.67
URN: urn:nbn:de:0030-drops-127364
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12736/
Lohrey, Markus ;
Zetzsche, Georg
Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups
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.
BibTeX - Entry
@InProceedings{lohrey_et_al:LIPIcs:2020:12736,
author = {Markus Lohrey and Georg Zetzsche},
title = {{Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {67:1--67:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12736},
URN = {urn:nbn:de:0030-drops-127364},
doi = {10.4230/LIPIcs.MFCS.2020.67},
annote = {Keywords: computational group theory, matrix problems, Baumslag-Solitar groups}
}
|
Keywords: |
|
computational group theory, matrix problems, Baumslag-Solitar groups |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
