A linear-time algorithm for the orbit problem over cyclic groups (Q303693): Difference between revisions

Let \(G\leq S_n\) be a permutation group given by its generators. Let \(\Gamma\) be an alphabet, then \(G\) acts on \(\Gamma^n\) by permuting the indices. The orbit problem asks if two input words are in the same orbit with respect to this action. In general this problem is as hard as the graph isomorphism problem (see [\textit{E. M. Clarke} et al., ``Exploiting symmetry in temporal logic model checking'', Formal Methods Syst. Des. 9, No. 1--2, 77--104 (1996; \url{doi:10.1007/BF00625969})]). The authors give a linear algorithm for the orbit problem when \(G\) is cyclic given by its generating permutation. They reduce the problem in linear time to solving a system of linear congruence equations. For the latter there exists a well-known linear algorithm assuming constant-time integer arithmetic operations. However, this algorithm runs in cubic time in the number of equations if the number of bit operations is measured. Therefore the authors provide a linear algorithm to solve a system of linear congruence equations in the bit complexity model, as well.