Membership problems in finite groups (Q6995148)

The authors investigate several classical and new membership problems in finite groups, focusing mainly on permutation groups. They prove that the subset sum problem, the knapsack problem and the rational subset membership problem are all \textsf{NP}-complete in symmetric groups \(S_m\), sharpening a result of \textit{E. M. Luks} [DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 11, 139--175 (1993; Zbl 0813.20004)] by showing that \textsf{NP}-completeness already holds for products of three cyclic permutation groups.\N\NThey further study the context-free membership problem in permutation groups, proving that it is \textsf{PSPACE}-complete in general but \textsf{NP}-complete when restricted to grammars of bounded Horton-Strahler number. Their upper bounds are established even in the black-box model of group computation. Applications are given to intersection non-emptiness problems for group \textsf{DFA}s (finite automata with group-labeled transitions) and a single context-free grammar, improving known complexity bounds.\N\NAmong other contributions, they show that membership in products like \(\langle g \rangle \langle h_1, h_2, h_3 \rangle \langle g \rangle\) is \textsf{NP}-complete when the \(h_i\) commute, refining the structure analyzed by Luks [loc. cit.]. Various new hardness results are obtained both for subset sum and for knapsack in symmetric groups, even under abelian restrictions.