Permutation Groups: A Complexity Overview
Ákos Seress · Cambridge University Press eBooks · 2003
In this chapter, we start the main topic of this book with an overview of permutation group algorithms. Polynomial-Time Algorithms In theoretical computer science, a universally accepted measure of efficiency is polynomial-time computation . In the case of permutation group algorithms, groups are input by a list of generators. Given G = 〈 S 〉 ≤ S n , the input is of length | S | n and a polynomial-time algorithm should run in O ((| S | n ) c ) for some fixed constant c . In practice, | S | is usually small: Many interesting groups, including all finite simple groups, can be generated by two elements, and it is rare that in a practical computation a permutation group is given by more than ten generators. On the theoretical side, any G ≤ S n can be generated by at most n /2 permutations (cf. [McIver and Neumann, 1987]). Moreover, any generating set S can be easily reduced to less than n 2 generators in O (| S | n 2 ) time by a deterministic algorithm (cf. Exercise 4.1), and in Theorem 10.1.3 we shall describe how to construct at most n – 1 generators for any G ≤ S n . Hence, we require that the running time of a polynomial-time algorithm is O ( n c + | S | n 2 ) for some constant c . In this book, we promote a slightly different measure of complexity involving n , | S |, and log | G | (cf. Section 3.2), which better reflects the practical performance of permutation group algorithms.