The power word problem of a group $G$ asks whether an expression $p_1^{x_1} \dots p_n^{x_n}$, where the $p_i$ are words and the $x_i$ binary encoded integers, is equal to the identity of $G$. We show that the power word problem in a fixed graph product is $\mathsf{AC}^0$-Turing-reducible to the word problem of the free group $F_2$ and the power word problem of the base groups. Furthermore, we look into the uniform power word problem in a graph product, where the dependence graph and the base groups are part of the input. Given a class of finitely generated groups $\mathcal{C}$, the uniform power word problem in a graph product can be solved in $\mathsf{AC^0(C_=L^{PowWP\mathcal{C}})}$. As a consequence of our results, the uniform knapsack problem in graph groups is $\mathsf{NP}$-complete.
翻译：$G$组的功率单词问题询问一个表达式 $p_ 1 ⁇ x_ 1}\ dots p_n ⁇ x_n}$, 其中$p_i$是单词和$x_i$二进制整数, 是否等于$G$。 我们显示, 固定图形产品中的功率单词问题是$\mathsf{AC}0( C ⁇ L ⁇ PowWP\mathcal{C ⁇ } ) 的单词问题, 以及基组的功率单词问题。 此外, 我们查看图表产品中统一功率单词问题, 其中依赖性图表和基组是输入的一部分。 鉴于一个有限生成的组 $\mathcal{C} 美元, 图形产品中的统一功率单词问题可以用$\mathsf{C} 来解决 。 由于我们的结果, 图形组的统一Knapsack问题是$mathfs\\\fn}- 完全。
相关内容
微信扫码咨询专知VIP会员