05 Fakultät Informatik, Elektrotechnik und Informationstechnik

The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell in (Inf. Comput. 178 (1), 253-262, 10 ) where they showed that this problem is in P for nilpotent groups while it is NP -complete for non-solvable groups. Since then, several results have appeared showing that the problem can be solved in polynomial time in certain solvable groups G having a nilpotent normal subgroup H with nilpotent factor G / H . This paper shows that such a normal subgroup must exist in each finite group with equation satisfiability solvable in polynomial time, unless the Exponential Time Hypothesis fails.

The power word problem for a group Gasks whether an expression u1x1⋯unxn, where the uiare words over a finite set of generators of Gand the xibinary encoded integers, is equal to the identity of G. It is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over G). We start by showing some easy results concerning the power word problem. In particular, the power word problem for a group Gis uNC1-many-one reducible to the power word problem for a finite-index subgroup of G. For our main result, we consider graph products of groups that do not have elements of order two. We show that the power word problem in a fixed such graph product is AC0-Turing-reducible to the word problem for the free group F2and the power word problems 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 Cwithout order two elements, the uniform power word problem in a graph product can be solved in AC0[C=LUPowWP(C)], where UPowWP(C)denotes the uniform power word problem for groups from the class C. As a consequence of our results, the uniform knapsack problem in right-angled Artin groups is NP-complete. The present paper is a combination of the two conference papers (Lohrey and Weiß 2019b, Stober and Weiß 2022a). In Stober and Weiß (2022a) our results on graph products were wrongly stated without the additional assumption that the base groups do not have elements of order two. In the present work we correct this mistake. While we strongly conjecture that the result as stated in Stober and Weiß (2022a) is true, our proof relies on this additional assumption.

05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Browse

Filters

Settings

Sort By

Results per page

Search Results