Computing commutator length is hard

The commutator length $c{l}_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$isNP-complete\mathrm{.}Thus,unlessP=NP,thereisnoalgorithmthatcomputes$cl_G(g)$inpolynomialtimeintermsof$|g|$,thewordlengthof$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.