TY - JOUR
T1 - The word and geodesic problems in free solvable groups
AU - Myasnikov, A.
AU - Roman'kov, V.
AU - Ushakov, A.
AU - Vershik, A.
PY - 2010/9
Y1 - 2010/9
N2 - 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 S r,dinto 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(rn log2 n) in Sr,2, and O(3rd) 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(n3rd); 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 relatively new geometric ideas; in particular, we establish a direct link between Fox derivatives and geometric flows on Cayley graphs.
AB - 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 S r,dinto 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(rn log2 n) in Sr,2, and O(3rd) 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(n3rd); 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 relatively new geometric ideas; in particular, we establish a direct link between Fox derivatives and geometric flows on Cayley graphs.
KW - Fox derivatives
KW - Free solvable groups
KW - Geodesic problem
KW - Steiner tree problem
KW - Theoretical computer science
KW - Word problem
UR - http://www.scopus.com/inward/record.url?scp=77952082909&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77952082909&partnerID=8YFLogxK
U2 - 10.1090/S0002-9947-10-04959-7
DO - 10.1090/S0002-9947-10-04959-7
M3 - Article
AN - SCOPUS:77952082909
SN - 0002-9947
VL - 362
SP - 4655
EP - 4682
JO - Transactions of the American Mathematical Society
JF - Transactions of the American Mathematical Society
IS - 9
ER -