Algorithmic stratification of the conjugacy problem in Miller’s groups
Algorithmic stratification of the conjugacy problem in Miller’s groups
复制标题
米勒群共轭问题的算法分层
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
V. Remeslennikov
中科院分区：
文献类型：
--
作者：
A. Borovik;A. Myasnikov;V. Remeslennikov;V. Remeslennikov
讨论了米勒群上共轭问题的复杂性.我们对所讨论的群进行分层，并表明对于“几乎所有”（在某种明确的意义上）元素，共轭搜索问题在立方时间中是可判定的。值得注意的是，一个米勒的群可能有不可判定的共轭搜索问题，我们的结果表明，“硬”的问题的情况下，包括一个可忽略的小部分的群体。
We discuss the complexity of conjugacy problem in Miller’s groups. We stratify the groups in question and show that for “almost all”, in some explicit sense, elements, the conjugacy search problem is decidable in cubic time. It is worth noting that a Miller’a group may have undecidable conjugacy search problem; our results show that “hard” instances of the problem comprise a negligibly small part of the group.