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 $Stab_{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