Intuitively, an SLP computing some g ∈ G is an efficient way of storing g as a group word over S; observe that if g is constructed in i steps, the word length of g may be exponential in i, but the length of the corresponding SLP is linear in i.
Straight-line programs were introduced by Babai and Szemerédi in 1984[1] as a tool for studying the computational complexity of certain matrix group properties.
Babai and Szemerédi prove that every element of a finite group G has an SLP of length O(log2|G|) in every generating set.
An efficient solution to the constructive membership problem is crucial to many group-theoretic algorithms.
Three oracles are provided for the group-theoretic functions of multiplication, inversion, and checking for equality with the identity.
Firstly, a sequence of abstract expressions requires less memory than terms over the generating set.
Straight-line programs can be used to study compression of finite groups via first-order logic.
[3] Straight-line programs computing generating sets for maximal subgroups of finite simple groups.
The online ATLAS of Finite Group Representations[4] provides abstract straight-line programs for computing generating sets of maximal subgroups for many finite simple groups.
The following is a straight-line program that computes a generating set for a maximal subgroup E32·E32⋊C31.
This straight-line program can be found in the online ATLAS of Finite Group Representations.
The reachability theorem states that, given a finite group G generated by S, each g ∈ G has a maximum cost of (1 + lg|G|)2.
The Cayley graph of G is connected and if i < s, K(i)−1K(i) ≠ G, then there is an element of the form g1·g2 ∈ G \ K(i)−1K(i) with g1 ∈ K(i)−1K(i) and g2 ∈ S. It takes at most 2i steps to generate g1 ∈ K(i)−1K(i).