3
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ What do you mean by "constant polynomials"? $\endgroup$ – D.W. Apr 4 '16 at 2:57
  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 4 '16 at 3:13
  • $\begingroup$ @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$.) $\endgroup$ – Thomas Klimpel Apr 4 '16 at 6:44
  • $\begingroup$ 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. $\endgroup$ – Thomas Klimpel Sep 28 '16 at 6:49
  • $\begingroup$ 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 ℤ. $\endgroup$ – Thomas Klimpel Sep 28 '16 at 9:18
2
$\begingroup$

The blog post you link to already gives a deterministic polynomial-time (in fact, linear-time) algorithm for the word problem over a free group with 2 letters.

In contrast, no deterministic polynomial-time algorithm for identity testing for polynomials is currently known (this is a famous open problem).

Therefore, it's not likely to be easy to prove that the word problem over the free group is equivalent in complexity to identity testing of polynomials.


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}$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.