# What is the name of the word problem for free groups under straight line program encoding?

I believe that the word problem is the problem to decide whether two different expressions denote the same element of a suitably defined algebraic structure. For simplicity, let us focus on free groups here. (Because I'm only interested in free algebras, and for groups one might indeed call this a word problem.) The expressions $(b^{-1}c)^{-1}b^{-1}(ab^{-1})^{-1}$, $(ab^{-1}c)^{-1}$, and $a^{-1}bc^{-1}$ are examples of such expressions. The first and second expression denote the same element of the free group, while the third expression denotes a different element.

The straight line program encoding is basically the same concept as arithmetic circuits, without implicit commutativity. It is one of the natural encodings of elements for a free algebra. One way to define the straight line program encoding is like in definition 1.1 from one of the google results for straight line program: The straight line program encoding of $f$ is an evaluation circuit $\gamma$ for $f$, where the only operations allowed belong to $\{()^{-1},\cdot\}$. More precisely: $\gamma=(\gamma_{1-n},\dots,\gamma_0,\gamma_1,\dots,\gamma_L)$ where $f=\gamma_L$, $\gamma_{1-n}:=x_1,\dots,\gamma_0:=x_n$ and for $k>0$, $\gamma_k$ is one of the following forms: $\gamma_k=(\gamma_j)^{-1}$ or $\gamma_k=\gamma_i\cdot\gamma_j$ where $i,j<k$.

The application of the operation $()^{-1}$ can easily be restricted to $\gamma_k=(\gamma_j)^{-1}$ for $j\leq 0$ without increasing $L$ to more than $2L+n$. This means that we are basically talking about words over the alphabet $\{x_1,\dots,x_n,(x_1)^{-1},\dots,(x_n)^{-1}\}$, hence the name "word problem" makes sense. But it seems a bad name for the general problem to decide whether two elements of a free algebra given by straight line programs are identical. It might be called identity testing.

Does the problem (to decide whether two elements of a free algebra given by straight line programs are identical) already has an established name, or is there a good name for this problem?

Maybe a better idea would be to give a name to the complementary problem, i.e. the problem to distinguish two different elements of a free algebra. So calling it slp distinction problem for free groups (commutative rings, commutative inverse rings, Boolean rings, ...) could work, because straight line program (slp) is a long name (but good and descriptive nevertheless). The advantage of naming the complementary problem is that we get problems in RP and NP, instead of problems in co-RP and co-NP.

The computational complexity of this problem is not worse than that of identity testing of constant polynomials over $\mathbb Z$ in straight line program encoding (no variables, i.e. $n=0$, but the straight line programs allow to compactly encode huge numbers): Using the same approach as in the dlog-space algorithm for the normal word problem, the problem can be reduced to deciding whether the product of integer 2x2 matrices equals the identity matrix. (The word problem over $n$ letters easily embeds into the word problem over $2$ letters, for example you can replace $a$, $b$, $c$, $d$ by $aa$, $ab$, $ba$, and $bb$.) So the problem is in randomized polynomial time (RP) (or rather co-RP). However, I didn't manage to show that it is actually equivalent (in complexity) to identity testing of (constant) polynomials over $\mathbb Z$, as I initially hoped. (This is unrelated to the answer by D.W., which rather shows that the significance of straight line encoding is currently not widely appreciated.)

• What do you mean by "constant polynomials"? – D.W. Apr 4 '16 at 2:57
• Also, your statement about 2x2 matrices is a bit off: it's correct that the word problem for the free group over 2 letters can be reduced to a question about 2x2 matrices, but do note the restriction to the free group over 2 letters. I don't think the same result applies to the free group over $n$ letters. – D.W. Apr 4 '16 at 3:13
• @D.W. I added short explanation in parenthesis to the question: (no variables, i.e. $n=0$ but the straight line programs allow to compactly encode huge numbers) and (The word problem over $n$ letters easily embeds into the word problem over $2$ letters, for example you can replace $a$, $b$, $c$, $d$ by $aa$, $ab$, $ba$, and $bb$.) – Thomas Klimpel Apr 4 '16 at 6:44
• I finally found something... Markus Lohey has called them compressed word problems, see eti.uni-siegen.de/ti/veroeffentlichungen/04-siam.pdf and arxiv.org/pdf/1106.1000v1.pdf. – Thomas Klimpel Sep 28 '16 at 6:49
• And the compressed word problem for free groups is in P, see eti.uni-siegen.de/ti/veroeffentlichungen/cwp-brief.pdf. So it is (most probably) not equivalent to identity testing of (constant) polynomials over ℤ. – Thomas Klimpel Sep 28 '16 at 9:18

The "straight-line encoding" doesn't seem to change the complexity of the word problem in any interesting way. It seems equivalent to simply specifying the input as an expression (i.e., a sequence of symbols, where each symbol is either $x_i$ or $x_i^{-1}$).