On the Complexity of the Whitehead Minimization Problem
On the Complexity of the Whitehead Minimization Problem
复制标题
关于怀特海最小化问题的复杂性
DOI：
--
复制
发表时间：
2006
影响因子：
0.8
通讯作者：
P. Weil
中科院分区：
文献类型：
--
作者：
Abdó Roig;E. Ventura;P. Weil
怀特海最小化问题在于在词、循环词或有限秩自由群中的有限生成子群的自同轨道中找到最小尺寸元素。我们给出了第一个完全多项式算法来解决这个问题，即输入词的长度和自由组的秩都是多项式的算法。早期的算法对自由组的排名具有指数依赖性。由此可见，原性问题（决定一个词是否是自由群的某个基的元素）和自由因子问题也可以在多项式时间内解决。
The Whitehead minimization problem consists in finding a minimum size element in the automorphic orbit of a word, a cyclic word or a finitely generated subgroup in a finite rank free group. We give the first fully polynomial algorithm to solve this problem, that is, an algorithm that is polynomial both in the length of the input word and in the rank of the free group. Earlier algorithms had an exponential dependency in the rank of the free group. It follows that the primitivity problem — to decide whether a word is an element of some basis of the free group — and the free factor problem can also be solved in polynomial time.