文章基本信息

标题：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