DROPS

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2023.134

On the Complexity of Diameter and Related Problems in Permutation Groups

Authors: Markus Lohrey and Andreas Rosowski

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract

We prove that it is Π₂^𝖯-complete to verify whether the diameter of a given permutation group G = ⟨A⟩ is bounded by a unary encoded number k. This solves an open problem from a paper of Even and Goldreich, where the problem was shown to be NP-hard. Verifying whether the diameter is exactly k is complete for the class consisting of all intersections of a Π₂^𝖯-language and a Σ₂^𝖯-language. A similar result is shown for the length of a given permutation π, which is the minimal k such that π can be written as a product of at most k generators from A. Even and Goldreich proved that it is NP-complete to verify, whether the length of a given π is at most k (with k given in unary encoding). We show that it is DP-complete to verify whether the length is exactly k. Finally, we deduce from our result on the diameter that it is Π₂^𝖯-complete to check whether a given finite automaton with transitions labelled by permutations from S_n produces all permutations from S_n.

Cite as

Markus Lohrey and Andreas Rosowski. On the Complexity of Diameter and Related Problems in Permutation Groups. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 134:1-134:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lohrey_et_al:LIPIcs.ICALP.2023.134,
  author =	{Lohrey, Markus and Rosowski, Andreas},
  title =	{{On the Complexity of Diameter and Related Problems in Permutation Groups}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{134:1--134:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.134},
  URN =		{urn:nbn:de:0030-drops-181864},
  doi =		{10.4230/LIPIcs.ICALP.2023.134},
  annote =	{Keywords: algorithms for finite groups, diameter of permutation groups, rational subsets in groups}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2022.71

Membership Problems in Finite Groups

Authors: Markus Lohrey, Andreas Rosowski, and Georg Zetzsche

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

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.

Cite as

Markus Lohrey, Andreas Rosowski, and Georg Zetzsche. Membership Problems in Finite Groups. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.MFCS.2022.71},
  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}
}

Search Results

Documents authored by Rosowski, Andreas

On the Complexity of Diameter and Related Problems in Permutation Groups

Abstract

Cite as

Membership Problems in Finite Groups

Abstract

Cite as

Thanks for your feedback!

Could not send message