文章基本信息
- 标题：Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups
- 本地全文：下载
- 作者：Markus Lohrey ; Georg Zetzsche
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：170
- 页码：67:1-67:15
- DOI：10.4230/LIPIcs.MFCS.2020.67
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：We prove that the power word problem for the solvable Baumslag-Solitar groups BS(1,q) = âY¨ a,t â^£ t a t^{-1} = a^q âY© 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.
- 关键词：computational group theory; matrix problems; Baumslag-Solitar groups
