A fast algorithm to the conjugacy problem on generic braids
A fast algorithm to the conjugacy problem on generic braids
复制标题
通用辫子共轭问题的快速算法
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
J. W. Lee
中科院分区：
文献类型：
--
作者：
K. Ko;J. W. Lee
通过分析随机辫子在 Garside 加权分解和循环下的行为，研究了通过乘以随机选择的排列辫子而形成的随机辫子。利用这种分析，我们提出了一种解决共轭问题的多项式时间算法，该算法以压倒性的概率成功地解决了随机辫子问题。随着辫子指数或排列辫子因子数量的增加，成功概率收敛到 1，因此，与普遍看法相反，共轭问题的硬实例分布变得越来越稀疏。我们还证明了 Birman 和 Gonz'{a}lez-Meneses 的猜想，即任何伪阿诺索夫辫子在通电和循环后都可以进行特殊的加权分解。此外，我们给出了功率和所需迭代循环次数的多项式上限。
Random braids that are formed by multiplying randomly chosen permutation braids are studied by analyzing their behavior under Garside's weighted decomposition and cycling. Using this analysis, we propose a polynomial-time algorithm to the conjugacy problem that is successful for random braids in overwhelming probability. As either the braid index or the number of permutation-braid factors increases, the success probability converges to 1 and so, contrary to the common belief, the distribution of hard instances for the conjugacy problem is getting sparser. We also prove a conjecture by Birman and Gonz\'{a}lez-Meneses that any pseudo-Anosov braid can be made to have a special weighted decomposition after taking power and cycling. Moreover we give polynomial upper bounds for the power and the number of iterated cyclings required.