English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We study the computational complexity of the Word Problem (WP) in freesolvable groups $S_{r,d}$, where $r \geq 2$ is the rank and $d \geq 2$ is thesolvability 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 ina fixed group $S_{r,d}$. Unfortunately, the degree of the polynomial growstogether with $d$, so the uniform algorithm is not polynomial in $d$. In thispaper 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 aseemingly close problem of computing the geodesic length of elements in$S_{r,2}$ is $NP$-complete. We prove also that one can compute Fox derivativesof elements from $S_{r,d}$ in time $O(n^3 r d)$, in particular one can useefficiently the Magnus embedding in computations with free solvable groups. Ourapproach is based on such classical tools as the Magnus embedding and Foxcalculus, as well as, on a relatively new geometric ideas, in particular, weestablish a direct link between Fox derivatives and geometric flows on Cayleygraphs.

The word and geodesic problems in free solvable groups