2008/07/07 by A. Myasnikov, Alexei Myasnikov, В. А. Романьков +9 · 1 citation
Computer Science · Mathematics · #20F10 #20F16 #20F65 #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #Logic, programming, and type systems #math.CO #math.GR #msc:20F10 #msc:20F16 #msc:20F65 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0807.1032
32pp. Ref 55
arxiv created 2008/07/07 · openalex publication_date 2008/07/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the computational complexity of the Word Problem (WP) in free solvable groups Sr,d, where r ≥ 2 is the rank and d ≥ 2 is the solvability class of the group. It is known that the Magnus embedding of Sr,d into matrices provides a polynomial time decision algorithm for WP in a fixed group Sr,d. Unfortunately, the degree of the polynomial grows together with d, so the uniform algorithm is not polynomial in d. In this paper we show that WP has time complexity O(r n log2 n) in Sr,2, and O(n3 r d) in Sr,d for d ≥ 3. However, it turns out, that a seemingly close problem of computing the geodesic length of elements in Sr,2 is NP-complete. We prove also that one can compute Fox derivatives of elements from Sr,d in time O(n3 r d), in particular one can use efficiently the Magnus embedding in computations with free solvable groups. Our approach is based on such classical tools as the Magnus embedding and Fox calculus, as well as, on a relatively new geometric ideas, in particular, we establish a direct link between Fox derivatives and geometric flows on Cayley graphs.