Group Coset Equality (GCE)

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

Problem

Is $\langle U \rangle x = y \langle V \rangle$?

Status

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

Remarks

A polynomial time algorithm for the problem is given in [1]. The reduction to show hardness is from IS.

The following three decision problems are also $\P$-complete [1]:

1. Equality of Right Cosets — Does $\langle U \rangle x = \langle V \rangle y$?,
2. Equivalence of Cosets — Are there $x, y$ such that $\langle U \rangle x = y \langle V \rangle$?, and
3. Equivalence of Right Cosets — Are there $x, y$ such that $\langle U \rangle x = \langle V \rangle y$?.