patternMinor
What is the name of the word problem for free groups under straight line program encoding?
Viewed 0 times
problemthegroupswhatfreelineprogramunderwordname
Problem
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 fo
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 fo
Solution
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}$).
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}$).
Context
StackExchange Computer Science Q#55413, answer score: 2
Revisions (0)
No revisions yet.