The minimum-length generator sequence problem is NP-hard

DOI10.1016/0196-6774(81)90029-8zbMath0467.68046DBLPjournals/jal/EvenG81OpenAlexW2023961800WikidataQ63628478 ScholiaQ63628478MaRDI QIDQ3920644

Oded Goldreich, Shimon Even

Publication date: 1981

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(81)90029-8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Permutation groups (20B99)

Related Items (26)

Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Computing short generator sequences ⋮ Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement ⋮ Discrete logarithms for finite groups ⋮ Edge-foreward index of star graphs and other Cayley graphs ⋮ Cyclic group blocking polyhedra ⋮ The Time Complexity of the Token Swapping Problem and Its Parallel Variants ⋮ The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant ⋮ An algebraic view of bacterial genome evolution ⋮ A sharp diameter bound for unipotent groups of classical type over ℤ/pℤ ⋮ Approximation algorithms for sorting permutations by extreme block-interchanges ⋮ AN ALGORITHM FOR COMPUTATION OF THE GROWTH FUNCTIONS IN FINITE TWO-GENERATED GROUPS OF EXPONENT 5 ⋮ A resource-efficient algorithm for study the growth in finite two-generator groups of exponent 5 ⋮ Sorting permutations by block-interchanges ⋮ Growth in SL2 over finite fields ⋮ Some problems on Cayley graphs ⋮ The optimal routing of augmented cubes ⋮ Diameter bounds and recursive properties of Full-Flag Johnson graphs ⋮ Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings ⋮ Cryptographic Hash Functions and Expander Graphs: The End of the Story? ⋮ Vertex reconstruction in Cayley graphs ⋮ Sorting by bounded block-moves ⋮ Unnamed Item ⋮ On Applications of the Cayley Graphs of some Finite Groups of Exponent Five ⋮ The complexity of finding minimum-length generator sequences ⋮ Permutations of bounded degree generate groups of polynomial diameter

This page was built for publication: The minimum-length generator sequence problem is NP-hard