论文标题
计算换向器长度很难
Computing commutator length is hard
论文作者
论文摘要
$ g \ in [g，g] $的换向器长度$ cl_g（g）$是组$ g $的换向器子组，是表达$ g $作为其产品所需的最少的换向器。 如果$ g $是一个非亚洲自由组，则给出一个整数$ n \ in \ mathbb {n} $和[g，g] $中的元素$ g \ in [g，g] $确定$ cl_g（g）\ leq n $是np-complete的决策问题。因此，除非p = np，否则没有算法在多项式时间内计算$ cl_g（g）$，以$ | g | $，$ g $的单词lordlength。对于缩回非亚伯自由群体的群体，例如非亚伯利亚右角Artin群体，此陈述仍然是正确的。 我们将通过将换向器长度与单词的\ emph {cyclak block互换距离}联系起来来显示这些语句，我们也表明这是NP完整的。
The commutator length $cl_G(g)$ of an element $g \in [G,G]$ in the commutator subgroup of a group $G$ is the least number of commutators needed to express $g$ as their product. If $G$ is a non-abelian free groups, then given an integer $n \in \mathbb{N}$ and an element $g \in [G,G]$ the decision problem which determines if $cl_G(g) \leq n$ is NP-complete. Thus, unless P=NP, there is no algorithm that computes $cl_G(g)$ in polynomial time in terms of $|g|$, the wordlength of $g$. This statement remains true for groups which have a retract to a non-abelian free group, such as non-abelian right-angled Artin groups. We will show these statements by relating commutator length to the \emph{cyclic block interchange distance} of words, which we also show to be NP-complete.
