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 is the name of the word problem for free groups under straight line program encoding?
terminology;decision problem;group theory