2026-07-26T00:39:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16869 2024-03-06T10:58:32Z ddc:004 open_access

Membership Problems in Finite Groups Lohrey, Markus Rosowski, Andreas Zetzsche, Georg algorithms for finite groups intersection non-emptiness problems knapsack problems in groups 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Markus Lohrey and Andreas Rosowski and Georg Zetzsche 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.71 urn:nbn:de:0030-drops-168694 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.71 eng https://creativecommons.org/licenses/by/4.0/legalcode