On the Subgroup Distance Problem in Cyclic Permutation Groups

We show that the Subgroup distance problem regarding the Hamming distance, the Cayley distance and the $l_{\mathrm{\infty }}$ distance is NP-complete when the input group is cyclic. When we restrict the $l_{\mathrm{\infty }}$ distance to fixed values we show that it is NP-complete to decide whether there are numbers $z_1,z_2\in \mathbb{N}$ such that $l_{\mathrm{\infty }}(\beta ,{\alpha }_1^{z_1}{\alpha }_2^{z_2})\le 1$ for permutation ${\alpha }_1,{\alpha }_2,\beta \in S_n$ where ${\alpha }_1$ and ${\alpha }_2$ commute. However on the positive side we can show that it can be decided in NL whether there is a number $z\in \mathbb{N}$ such that $l_{\mathrm{\infty }}(\beta ,{\alpha }^z)\le 1$ for permutations $\alpha ,\beta \in S_n$. For the former we provide a tool, namely for all numbers $t_1,t_2,t\in \mathbb{N}$ where $t$ is required to be odd, $0\le t_1<t_2<t$ and $t_1\equiv ̸t_{2}q$ for all primes $q\mid t$ we give a constructive proof for the existence of permutations $\alpha ,\beta \in S_t$ with $l_{\mathrm{\infty }}(\beta ,{\alpha }^{t_1})\le 1$ and $l_{\mathrm{\infty }}(\beta ,{\alpha }^{t_2})\le 1$.