论文标题
同时共轭问题的次级算法
A subquadratic algorithm for the simultaneous conjugacy problem
论文作者
论文摘要
对称群体$ s_n $中的$ d $ - 中等性别问题询问是否存在S_n $中的排列$τ\，以至于$ b_j =τ=τ^{ - 1} a_j f hist of $ j = 1,2，$ j = 1,2，d $ $ b_2，\ ldots，b_d $以$ s_n $为单位的排列序列。解决问题的现有算法的时间复杂性为$ O（DN^2）$。我们表明，对于给定的正整数$ d $ $ d $ - 中等的共轭问题，可以在$ o（n^2）$ time中解决$ s_n $。
The $d$-Simultaneous Conjugacy problem in the symmetric group $S_n$ asks whether there exists a permutation $τ\in S_n$ such that $b_j = τ^{-1}a_j τ$ holds for all $j = 1,2,\ldots, d$, where $a_1, a_2,\ldots , a_d$ and $b_1, b_2,\ldots , b_d$ are given sequences of permutations in $S_n$. The time complexity of existing algorithms for solving the problem is $O(dn^2)$. We show that for a given positive integer $d$ the $d$-Simultaneous Conjugacy problem in $S_n$ can be solved in $o(n^2)$ time.
