Conjugacy in Baumslag’s Group, Generic Case Complexity, and Division in Power Circuits

The conjugacy problem is the following question: given two words

x

,

y

over generators of a fixed group

G

, decide whether

x

and

y

are conjugated, i.e., whether there exists some

z

such that

zx

z

− 1

 = 

y

in

G

. The conjugacy problem is more difficult than the word problem, in general. We investigate the conjugacy problem for two prominent groups: the Baumslag-Solitar group

BS

1,2

and the Baumslag(-Gersten) group

G

1,2

. The conjugacy problem in

BS

1,2

is

TC

0

-complete. To the best of our knowledge

BS

1,2

is the first natural infinite non-commutative group where such a precise and low complexity is shown. The Baumslag group

G

1,2

is an HNN-extension of

BS

1,2

and its conjugacy problem is decidable

G

1,2

by a result of Beese (2012). Here we show that conjugacy in

G

1,2

can be solved in polynomial time in a strongly generic setting. This means that essentially for all inputs conjugacy in

G

1,2

can be decided efficiently. In contrast, we show that under a plausible assumption the average case complexity of the same problem is non-elementary. Moreover, we provide a lower bound for the conjugacy problem in

G

1,2

by reducing the division problem in power circuits to the conjugacy problem in

G

1,2

. The complexity of the division problem in power circuits is an open and interesting problem in integer arithmetic.