Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.71
URN: urn:nbn:de:0030-drops-168694
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16869/
Lohrey, Markus ; Rosowski, Andreas ; Zetzsche, Georg
Membership Problems in Finite Groups
| pdf-format: |
|
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 ≥ 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 [Eugene M. Luks, 1991], 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.
BibTeX - Entry
@InProceedings{lohrey_et_al:LIPIcs.MFCS.2022.71,
author = {Lohrey, Markus and Rosowski, Andreas and Zetzsche, Georg},
title = {{Membership Problems in Finite Groups}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {71:1--71:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16869},
URN = {urn:nbn:de:0030-drops-168694},
doi = {10.4230/LIPIcs.MFCS.2022.71},
annote = {Keywords: algorithms for finite groups, intersection non-emptiness problems, knapsack problems in groups}
}
| Keywords: | algorithms for finite groups, intersection non-emptiness problems, knapsack problems in groups | |
| Seminar: | 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 22.08.2022 |
