Straight-line complexity

Definition

Note that the actual definition of straight-line complexity as a numerical value varies a lot with the convention. What's more important is the ballpark of the definition.

Definition for a word computation problem

Consider a word $w$ in the letters $x_{1},x_{2},\dots ,x_{n}$. The straight-line complexity of the problem of computing $w$ in terms of $x_{1},x_{2},\dots ,x_{n}$ is defined as 0 if $w$ is the trivial word or $w=x_{i}$ for some $i$. Otherwise, it is the smallest positive integer $m$ such that we can construct the following:

• A sequence $w_{1},w_{2},\dots ,w_{m}$ of words in $x_{1},x_{2},\dots ,x_{n}$ such that $w_{m}=w$
• An expression for each $w_{i}$ as either of these:
  • the inverse of an element $u$ where $u$ is in $\{x_{1},x_{2},\dots ,x_{n},w_{1},\dots ,w_{m-1}\}$
  • the product of two elements $uv$ where both $u$ and $v$ are in $\{x_{1},x_{2},\dots ,x_{n},w_{1},\dots ,w_{m-1}\}$

The above definition of straight line complexity treats each multiplication and inversion operation as costing one line of complexity. We can define a more general straight-line complexity that associates different weights to multiplication and inversion, and then seeks to minimize the appropriately weighted combination of the multiplication and inversion steps.

Definition for a problem of computing multiple words

PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]

One of the people editing this page intended to fill in this information at a later stage, but hasn't gotten around to doing it yet. If you see this placeholder for a long time, file an error report at the error reporting page.

Examples

For words in one letter, i.e., powers

Consider the word $w=x^{n}$ in one letter $x$ where $n$ is a positive integer. The straight-line complexity of this word is at most $\lfloor \log _{2}n\rfloor +b(n)-1$ where $b(n)$ is the number of ones that appear in the binary expansion of $n$. In fact, that is the best we can achieve if we are forbidden from using inverses. The algorithm is as follows: write the binary expansion of $n$. By repeated squaring, compute $x^{2^{k}}$ for all relevant powers, and then multiply them.

If we are allowed to use inverses, the expression becomes a little more complicated. The smallest $n$ for which using inverses allows for a concrete saving is $n=31$ (not using inverses would require 8 steps, whereas using inverses, we can compute $x^{32}$, $x^{-1}$, and then multiply, using 7 steps).

The general formula seems to be:

$\min\{\lfloor \log _{2}n\rfloor +b(n)-1,2\lfloor \log _{2}n\rfloor +4-b(n)\}$

For negative numbers $n$, the formula seems to be:

$\min\{\lfloor \log _{2}n\rfloor +b(n),2\lfloor \log _{2}n\rfloor +4-b(n)\}$

For words in two letters

PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]

One of the people editing this page intended to fill in this information at a later stage, but hasn't gotten around to doing it yet. If you see this placeholder for a long time, file an error report at the error reporting page.

Relation with word length

The straight-line complexity of a word in $n$ letters is related to its word length in two obvious ways. Let $m$ be the straight-line complexity and $\ell$ be the word length. Then:

• $\ell \leq 2^{m}$: This is because each step of the program can at most double the length of the longest word constructed so far.
• $m\leq \min\{n,\ell \}+\ell -1$: Note that if the word does not involve inverses, $m\leq \ell -1$ for the obvious reason that we can multiply two at a time. If the word involves inverses, then we may need to perform inversion operations. We need to perform at most $\min\{n,\ell \}$ inversion operations.

Facts

• Babai-Szemeredi reachability lemma says that for any element in a finite group $G$ and any generating set for the finite group, there is a word for the element in terms of the generating set that has straight line complexity $(1+\log _{2}|G|)^{2}$.