Set transporter problem

This problem is polynomial-time equivalent to the following basic problem: set-stabilizer problem

Description

Given data

We are given a group $G$ acting on a set $S$ specified via a (small) generating set $A$ comprising permutations. We are given two subsets $T_{1}$ and $T_{2}$ of $G$ .

Goal

We need to find whether there exists a $g \in G$ such that $T_{1}^{g} = T_{2}$ .

Relation with other problems

Equivalent decision problems

Coset intersection problem: The reduction from set transporter to coset intersection follows directly from the fact that the set of elements in $g$ sending $T_{1}$ to $T_{2}$ is $G \cap C$ where $C$ is a coset of $S t a b_{G} (T_{1})$ . The reduction the other way around involves looking at the action on $S \times S$ and asking whether there is an element sending the diagonal to a particular subset. (This idea is very similar to the idea used in showing that the group intersection problem and set-stabilizer problem are equivalent).

For full proof, refer: Coset intersection PTIME equals set transporter

Group factorization problem: The equivalence of this follows easily from the fact that it is equivalent to the coset intersection problem.
Double coset membership testing problem: The equivalence of this again follows easily from the fact that it is equivalent to the coset intersection problem.
Set-stabilizer problem