Generalized Word Problem (GWP)

Input

Let $S$ be a finite set and $F$ be the free group generated by $S$. Let $\overline{S} = \{s, s^{-1} \mid s \in S\}$, where $s^{-1}$ denotes the inverse of $s$. Let $\overline{S}^\ast$ denote the set of all finite words over $\overline{S}$. Let $U = \{u_1, \ldots, u_m\} \subseteq \overline{S}^\ast$, where $m \in \N$ and let $x \in \overline{S}^\ast$.

Problem

Is $x \in \langle U \rangle$? That is, is $x$ in the subgroup of $F$ generated by $U$?

Status

$\P$-complete (Avenhaus and Madlener [1], Stewart [2]).

Remarks

Stewart reported an error in [1]. The reduction in [1] is a generic one from a normal form Turing machine. However, it reduces a Turing machine computation to a version of GWP where $S$ is a countably infinite set [2]. Stewart shows using the Nielsen reduction algorithm that this problem is still in $\P$. Stewart calls this $\P$-complete problem the Generalized Word Problem for Countably-generated Free Groups (GWPC). He shows that GWPC is logarithmic space reducible to GWP; this, proving GWP is $\P$-complete as well [2].

For a natural number $k$, $\text{GWPC}(k)$ and $\text{GWPC}(\leq k)$ are the generalized word problems for finitely-generated subgroups of countably-generated free groups where all words involved are of length exactly $k$ and at most $k$, respectively. Stewart shows $\text{GWPC}(k)$ and $\text{GWPC}(\leq k)$ are $\P$-complete for $k$ greater than two [3]. When $k$ equals two the problems are complete for symmetric logarithmic space ($\mathsf{SLOG}$). The Word Problem for a Free Group is to decide whether $x$ equals the empty word in $F$. This problem is solvable in deterministic log space (Lipton and Zalcstein [4]).