Improved parallel algorithms for generalized Baumslag groups

Abstract: The Baumslag group had been a candidate for a group with an extremely difficult word problem until Myasnikov, Ushakov, and Won succeeded to show that its word problem can be solved in polynomial time. Their result used the newly developed data structure of power circuits allowing for a non-elementary compression of integers. Later this was extended in two directions: Laun showed that the same applies to generalized Baumslag groups

m a t h b f G_{1, q}

for

q g e q 2

and we established that the word problem of the Baumslag group

m a t h b f G_{1, 2}

can be solved in

m a t h s f {T C}^{2}

. In this work we further improve upon both previous results by showing that the word problem of all the generalized Baumslag groups

m a t h b f G_{1, q}

can be solved in

m a t h s f {T C}^{1}

, even for negative

q

. Our result is based on using refined operations on reduced power circuits. Moreover, we prove that the conjugacy problem in

m a t h b f G_{1, q}

is strongly generically in

m a t h s f {T C}^{1}

(meaning that for most inputs it is in

m a t h s f {T C}^{1}

). Finally, for every fixed

g i n m a t h b f G_{1, q}

conjugacy to

g

can be decided in

m a t h s f {T C}^{1}

for all inputs.

Cites work

Cited in

(6)

This page was built for publication: Improved parallel algorithms for generalized Baumslag groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6164005)