Template:Harryalerta In mathematics, more specifically in computational algebra, a straight-line program of a certain group G generated by a set S is a sequence of elements of G such that any element of the sequence is an element of a set $S$ or is obtained from previous elements of the sequence.

It was defined by Babai and Szerémedi as a way to study complexity of computational properties of groups.

Table of contents

Formal definition of SLP and cost

Example

Reachabillity theorem

proof

Definition

Let $G$ be a group generated by a subset $S$, a straight line program is a sequence $L=(g_1,g_2,g_3,...,g_n)$ where each g_i is obtainable in 3 ways: $g_i \in S$, $g_i=g_m . g_n$ for some $m,n<i or $g_i={g_m}^{-1} for some $m<i$. We say that $L$ generates its elements and we define the cost $c(g)$ of some element $g\in G$ to be the length of the shortest straight line program containing $g$.

The process of construction a straight line program is similar to a predicate logic derivation, but instead of axioms there are generators of the group and the rule of inference are the group multiplication and the inversion function.

Example

In $D_12$, the group of symetries of a hexagon, being generated by one rotation $\rho$ and one reflection $\lambda$. We can create straight line program to generate $\lambda \rho^3$: \begin{enumerate} \lambda \rho \rho^2 \rho^3 \lambda \rho^3 \end{enumerate}

Reachability theorem

The reachability theorem states that given a finite group $G$ generated by $S$ each $g\in G$ has a maximum cost of $(1+ log_{2}|G|)^2$. It can be understood as a way to how hard it can be to generate an element of a group only operating with the generators. Since $D_12$ has 12 elements, the reachability theorem states that the any element can be generated by example we generated an element of $D_12$ with 5 steps,