论文标题
可解决的Baumslag-Solitar组中的背包和电源单词问题
Knapsack and the power word problem in solvable Baumslag-Solitar groups
论文作者
论文摘要
我们证明了$ \ MathSf {gl}（2，\ Mathbb {C}）$的某些Metabelian子组的电源单词问题（包括可溶解的Baumslag-Solitar组$ \ Mathsf {bs}（bs}（bs}（bs}（1，q）（1，q）类$ \ mathsf {tc}^0 $。在电源词问题中，输入由组元素$ g_1，\ ldots，g_d $和二进制编码的整数$ n_1，\ ldots，n_d $组成，询问是否$ g_1^{n_1} \ cdots g_d^{n_d} = 1 $ holds。此外，我们证明了$ \ mathsf {bs}（1，q）$的背包问题是$ \ m athsf {np} $ - 完成。在背包问题中，输入由组元素$ g_1，\ ldots，g_d，h $组成，并且询问公式是否$ g_1^{x_1} \ cdots g_d^{x_d} = h $在$ \ mathbb {n}^d $中具有解决方案。对于更通用的所谓指数方程系统的情况，可以多次发生指数变量$ x_i $的情况，我们表明可溶解性对于$ \ Mathsf {bs}（1，q）$不可证明。
We prove that the power word problem for certain metabelian subgroups of $\mathsf{GL}(2,\mathbb{C})$ (including the solvable Baumslag-Solitar groups $\mathsf{BS}(1,q) = \langle a,t \mid t a t^{-1} = a^q \rangle$) belongs to the circuit complexity class $\mathsf{TC}^0$. In the power word problem, the input consists of group elements $g_1, \ldots, g_d$ and binary encoded integers $n_1, \ldots, n_d$ and it is asked whether $g_1^{n_1} \cdots g_d^{n_d} = 1$ holds. Moreover, we prove that the knapsack problem for $\mathsf{BS}(1,q)$ is $\mathsf{NP}$-complete. In the knapsack problem, the input consists of group elements $g_1, \ldots, g_d,h$ and it is asked whether the equation $g_1^{x_1} \cdots g_d^{x_d} = h$ has a solution in $\mathbb{N}^d$. For the more general case of a system of so-called exponent equations, where the exponent variables $x_i$ can occur multiple times, we show that solvability is undecidable for $\mathsf{BS}(1,q)$.
