2026-08-07T01:51:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18186 2024-03-06T11:01:15Z ddc:004 open_access

On the Complexity of Diameter and Related Problems in Permutation Groups Lohrey, Markus Rosowski, Andreas algorithms for finite groups diameter of permutation groups rational subsets in groups 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Markus Lohrey and Andreas Rosowski 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.134 urn:nbn:de:0030-drops-181864 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.134 eng https://creativecommons.org/licenses/by/4.0/legalcode