Membership problems in finite groups
General theory for finite permutation groups (20B05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)
The authors investigate several classical and new membership problems in finite groups, focusing mainly on permutation groups. They prove that the subset sum problem, the knapsack problem and the rational subset membership problem are all \textsf{NP}-complete in symmetric groups \(S_m\), sharpening a result of \textit{E. M. Luks} [DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 11, 139--175 (1993; Zbl 0813.20004)] by showing that \textsf{NP}-completeness already holds for products of three cyclic permutation groups.\N\NThey further study the context-free membership problem in permutation groups, proving that it is \textsf{PSPACE}-complete in general but \textsf{NP}-complete when restricted to grammars of bounded Horton-Strahler number. Their upper bounds are established even in the black-box model of group computation. Applications are given to intersection non-emptiness problems for group \textsf{DFA}s (finite automata with group-labeled transitions) and a single context-free grammar, improving known complexity bounds.\N\NAmong other contributions, they show that membership in products like \(\langle g \rangle \langle h_1, h_2, h_3 \rangle \langle g \rangle\) is \textsf{NP}-complete when the \(h_i\) commute, refining the structure analyzed by Luks [loc. cit.]. Various new hardness results are obtained both for subset sum and for knapsack in symmetric groups, even under abelian restrictions.
- \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
- A Brief History of Strahler Numbers
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Computational Complexity
- Graph isomorphism in quasipolynomial time (extended abstract)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 475362 (Why is no real title available?)
- scientific article; zbMATH DE number 1849958 (Why is no real title available?)
- scientific article; zbMATH DE number 871949 (Why is no real title available?)
- scientific article; zbMATH DE number 3341276 (Why is no real title available?)
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
- Knapsack in graph groups
- Knapsack in hyperbolic groups
- Knapsack problems in groups
- Knapsack problems in products of groups
- MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
- Membership problems in finite groups
- Model checking LTL with regular valuations for pushdown systems
- On the complexity of intersecting regular, context-free, and tree languages
- On the complexity of intersection non-emptiness for star-free language classes
- On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
- On the membership problem for finite automata over symmetric groups
- On the rational subset problem for groups.
- Reachability analysis of communicating pushdown systems
- Stallings foldings and subgroups of free groups
- The complexity of finding minimum-length generator sequences
- The complexity of intersecting finite automata having few final states
- The complexity of knapsack problems in wreath products
- The minimum-length generator sequence problem is NP-hard
- The rational subset membership problem for groups: a survey
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 Q6995148)
