Word Length and Diameter in Permutation Groups

Markus Lohrey; Alexander Thumm

In the authors' words

The input for the binary diameter problem consists of explicitly represented permutations generating a finite group $G$ and a binary-encoded nonnegative integer $k$ . The question is whether every element of $G$ is a product of at most $k$ input generators. For the binary length problem, the input contains in addition a permutation $g \in G$ and it is asked whether $g$ is a product of at most $k$ input generators. We prove that the binary diameter problem is PSPACE-complete. When restricted to $2$ -step nilpotent groups, the binary diameter problem is shown to be complete for $Π_{2}^{P}$ , whereas the binary length problem is shown to be NP-complete. Without the restriction to $2$ -step nilpotent groups, the binary length problem is PSPACE-complete by a result of Jerrum.

Main resultLimitation the authors admit

Word Length and Diameter in Permutation Groups

In the authors' words

More on Algebra & number theory that day

The Odlyzko-Poonen Conjecture on Irreducibility of Random Polynomials

Solution to Dixmier's Problem about spectra of C*-algebras

Poincar\'e Duality and Quadratic Refinements over Laurent Rings

On Haagerup-Izumi fusion categories

Monoidal Gr\"obner systems and categories of affine Brauer type