The ‐Simultaneous Conjugacy problem in the symmetric group asks whether there exists a permutation such that holds for all , where and are given sequences of permutations in . The time complexity of existing algorithms for solving the problem is . We show that for a given positive integer the ‐Simultaneous Conjugacy problem in can be solved in time. Our algorithm solves a number of problems from various fields of mathematics and computer science.