Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Membership Problems in Finite Groups


Zetzsche,  Georg
Group G. Zetzsche, Max Planck Institute for Software Systems, Max Planck Society;

External Resource
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 327KB

(Publisher version), 765KB

Supplementary Material (public)
There is no public supplementary material available

Lohrey, M., Rosowski, A., & Zetzsche, G. (2022). Membership Problems in Finite Groups. In S. Szeider, R. Ganian, & A. Silva (Eds.), 47th International Symposium on Mathematical Foundations of Computer Science (pp. 1-16). Wadern: Schloss Dagstuhl. doi:10.4230/LIPIcs.MFCS.2022.71.

Cite as: https://hdl.handle.net/21.11116/0000-000A-BC99-6
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 $n \geq 3$,
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.