Intersection of Cosets (IC)

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 \cap y \langle V \rangle$ nonempty?

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 an arbitrary polynomial time Turing machine.

The Intersection of Right Cosets Problem and the Intersection of Left Cosets Problem are subproblems of the Intersection of Cosets Problems and they are both $\P$-complete as well. For example, the Right Coset Problem is $\P$-complete since $\langle U \rangle x \cap \langle V \rangle y$ is nonempty if and only if $\langle U \rangle xy^{-1} \cap e \langle V \rangle$ is nonempty, where $e$ denotes the empty word.