Mathematics – Group Theory
Scientific paper
2008-07-07
Mathematics
Group Theory
32pp. Ref 55
Scientific paper
We study the computational complexity of the Word Problem (WP) in free solvable groups $S_{r,d}$, where $r \geq 2$ is the rank and $d \geq 2$ is the solvability class of the group. It is known that the Magnus embedding of $S_{r,d}$ into matrices provides a polynomial time decision algorithm for WP in a fixed group $S_{r,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 \log_2 n)$ in $S_{r,2}$, and $O(n^3 r d)$ in $S_{r,d}$ for $d \geq 3$. However, it turns out, that a seemingly close problem of computing the geodesic length of elements in $S_{r,2}$ is $NP$-complete. We prove also that one can compute Fox derivatives of elements from $S_{r,d}$ in time $O(n^3 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.
Myasnikov Alexei
Roman'kov V.
Ushakov Alexander
Vershik Anatoly
No associations
LandOfFree
The Word and Geodesic Problems in Free Solvable Groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Word and Geodesic Problems in Free Solvable Groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Word and Geodesic Problems in Free Solvable Groups will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-561410