Membership Problems in Finite Groups

arXiv2206.11756MaRDI QIDQ6402973FDOQ6402973

Authors: Markus Lohrey, Andreas Rosowski, Georg Zetzsche 

Publication date: 23 June 2022

Abstract: We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obtain NP-completeness for every fixed $ngeq3$, where $n$ is the number of permutations in the knapsack equation. In other words: membership in products of three cyclic permutation groups is NP-complete. This sharpens a result of Luks, which states NP-completeness of the membership problem for products of three abelian permutation groups. We also consider the context-free membership problem in permutation groups and prove that it is PSPACE-complete but NP-complete for a restricted class of context-free grammars where acyclic derivation trees must have constant Horton-Strahler number. Our upper bounds hold for black box groups. The results for context-free membership problems in permutation groups yield new complexity bounds for various intersection non-emptiness problems for DFAs and a single context-free grammar.

Mathematics Subject Classification ID

Formal languages and automata (68Q45) General theory for finite permutation groups (20B05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

This page was built for publication: Membership Problems in Finite Groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402973)