Subgroup Containment (SC)

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\}$, $V = \{v_1, \ldots, v_p\}$ $\subseteq \overline{S}^\ast$, where $m, p \in \N$.

Problem

Is the group generated by $U$ a subgroup of the group generated by $V$?

Status

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

Remarks

A variant of the Nielsen reduction algorithm can be used to show the problem is in $\P$. The reduction to show hardness is from GWP.

Since $\langle U \rangle$ is a subgroup of $\langle V \rangle$ if and only if $\langle U \cup V \rangle$ is normal in $\langle V \rangle$, it follows that the Normal Subgroup Problem, which is also in $\P$, is $\P$-complete. The problem of determining whether $\langle U \rangle$ is normal in $\langle U, x \rangle$ is also $\P$-complete [1].