Document Open Access Logo

On the Complexity of Diameter and Related Problems in Permutation Groups

Authors Markus Lohrey , Andreas Rosowski

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.134.pdf
  • Filesize: 0.77 MB
  • 18 pages

Document Identifiers

Author Details

Markus Lohrey
  • Universität Siegen, Germany
Andreas Rosowski
  • Universität Siegen, Germany

Funding

Both authors were supported by the DFG research project Lo748/12-2.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ICALP.2023.134

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • algorithms for finite groups
  • diameter of permutation groups
  • rational subsets in groups

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: https://doi.org/10.1017/CBO9780511804090.
  2. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 684-697. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897542.
  3. László Babai, Robert Beals, and Ákos Seress. On the diameter of the symmetric group: polynomial bounds. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pages 1108-1112. SIAM, 2004. URL: https://dl.acm.org/doi/10.5555/982792.982956.
  4. László Babai and Thomas P. Hayes. Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pages 1057-1066. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070584.
  5. László Babai and Gábor Hetyei. On the diameter of random Cayley graphs of the symmetric group. Combinatorics, Probability & Computing, 1:201-208, 1992. URL: https://doi.org/10.1017/S0963548300000237.
  6. László Babai, Gábor Hetyei, William M. Kantor, Alexander Lubotzky, and Ákos Seress. On the diameter of finite groups. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, FOCS 1990, Volume II, pages 857-865. IEEE Computer Society, 1990. URL: https://doi.org/10.1109/FSCS.1990.89608.
  7. László Babai, William M. Kantor, and A. Lubotsky. Small-diameter Cayley graphs for finite simple groups. European Journal of Combinatorics, 10(6):507-522, 1989. URL: https://doi.org/10.1016/S0195-6698(89)80067-8.
  8. László Babai and Ákos Seress. On the diameter of Cayley graphs of the symmetric group. Journal of Combinatorial Theory, Series A, 49(1):175-179, 1988. URL: https://doi.org/10.1016/0097-3165(88)90033-7.
  9. László Babai and Ákos Seress. On the diameter of permutation groups. European Journal of Combinatorics, 13(4):231-243, 1992. URL: https://doi.org/10.1016/S0195-6698(05)80029-0.
  10. Liming Cai, Jianer Chen, Rodney G. Downey, and Michael R. Fellows. On the parameterized complexity of short computation and factorization. Archive for Mathematical Logic, 36(4-5):321-337, 1997. URL: https://doi.org/10.1007/s001530050069.
  11. Shimon Even and Oded Goldreich. The minimum-length generator sequence problem is NP-hard. Journal of Algorithms, 2(3):311-313, 1981. URL: https://doi.org/10.1016/0196-6774(81)90029-8.
  12. Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks. Polynomial-time algorithms for permutation groups. In Proceedings of the 21st Annual Symposium on Foundations of Computer Science, FOCS 1980, pages 36-41. IEEE Computer Society, 1980. URL: https://doi.org/10.1109/SFCS.1980.34.
  13. Harald A. Helfgott and Ákos Seress. On the diameter of permutation groups. Annals of Mathematics, 179(2):611-658, 2014. URL: https://doi.org/10.4007/annals.2014.179.2.4.
  14. William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences, 65(4):695-716, 2002. URL: https://doi.org/10.1016/S0022-0000(02)00025-9.
  15. Mark Jerrum. The complexity of finding minimum-length generator sequences. Theoretical Computer Science, 36:265-289, 1985. URL: https://doi.org/10.1016/0304-3975(85)90047-7.
  16. Arthur A. Khashaev. On the membership problem for finite automata over symmetric groups. Discrete Mathematics and Applications, 32(6):389-395, 2022. URL: https://doi.org/10.1515/dma-2022-0033.
  17. D. Kornhauser, G. Miller, and P. Spirakis. Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In Proceedings of the 25th IEEE Symposium on Foundations of Computer Science, FOCS 1984, pages 241-250. IEEE Computer Society Press, 1984. URL: https://doi.org/10.1109/SFCS.1984.715921.
  18. Markus Lohrey, Andreas Rosowski, and Georg Zetzsche. Membership problems in finite groups. In Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, volume 241 of LIPIcs, pages 71:1-71:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.MFCS.2022.71.
  19. Pierre McKenzie. Permutations of bounded degree generate groups of polynomial diameter. Information Processing Letters, 19(5):253-254, 1984. URL: https://doi.org/10.1016/0020-0190(84)90062-0.
  20. not A or B (https://cstheory.stackexchange.com/users/38066/not-a-or b). An analog of DP for the second level of the polynomial hierarchy. Theoretical Computer Science Stack Exchange. URL: https://cstheory.stackexchange.com/q/38776.
  21. Christos H. Papadimitriou and Mihalis Yannakakis. The complexity of facets (and some facets of complexity). Journal of Computer and System Sciences, 28(2):244-259, 1984. URL: https://doi.org/10.1016/0022-0000(84)90068-0.
  22. Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge. The diameter of the Rubik’s cube group is twenty. SIAM Journal of Discrete Mathematics, 27(2):1082-1105, 2013. URL: https://doi.org/10.1137/120867366.
  23. Ákos Seress. Permutation Group Algorithms. Cambridge Tracts in Mathematics. Cambridge University Press, 2003. URL: https://doi.org/10.1017/CBO9780511546549.
  24. Larry J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3(1):1-22, 1976. URL: https://doi.org/10.1016/0304-3975(76)90061-X.
  25. Craig A. Tovey. A simplified NP-complete satisfiability problem. Discrete Applied Mathematics, 8(1):85-89, 1984. URL: https://doi.org/10.1016/0166-218X(84)90081-7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact