# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Membership Problems in Finite Groups

##### External Resource

https://drops.dagstuhl.de/opus/volltexte/2022/16869/

(Publisher version)

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2206.11756.pdf

(Preprint), 327KB

LIPIcs-MFCS-2022-71.pdf

(Publisher version), 765KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Lohrey, M., Rosowski, A., & Zetzsche, G. (2022). Membership Problems in Finite
Groups. In S. Szeider, R. Ganian, & A. Silva (*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

##### 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 $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.

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.