TY - JOUR
T1 - Conjugacy in Baumslag’s Group, Generic Case Complexity, and Division in Power Circuits
AU - Diekert, Volker
AU - Myasnikov, Alexei G.
AU - Weiß, Armin
N1 - Publisher Copyright:
© 2016, Springer Science+Business Media New York.
PY - 2016/12/1
Y1 - 2016/12/1
N2 - The conjugacy problem asks whether two words over generators of a fixed group G are conjugated, i.e., it is the problem to decide on input words x, y whether there exists z such that zxz- 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 BS1 , 2 and the Baumslag group G1 , 2 (also known as Baumslag–Gersten group). The conjugacy problem in BS1 , 2 is complete for the circuit class TC0. To the best of our knowledge BS1 , 2 is the first natural infinite non-commutative group where such a precise and low complexity is shown. The Baumslag group G1 , 2 is an HNN-extension of BS1 , 2. Hence, decidability of the conjugacy problem in G1 , 2 outside the so-called “black hole” follows from Borovik et al. (Int J Algebra Comput 17(5/6):963–997, 2007). Decidability everywhere is due to Beese. Moreover, he showed exponential time for the set of elements which cannot be conjugated into BS1 , 2 (Beese 2012). Here we improve Beese’s result in two directions by showing that the conjugacy problem in G1 , 2 can be solved in polynomial time in a strongly generic setting. This means that essentially for all inputs, conjugacy in G1 , 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 G1 , 2 by reducing the divisibility problem in power circuits to the conjugacy problem in G1 , 2. The complexity of the divisibility problem in power circuits is an open and interesting problem in integer arithmetic. We conjecture that it cannot be solved in elementary time because we can show that it cannot be solved in elementary time by calculating modulo values in power circuits.
AB - The conjugacy problem asks whether two words over generators of a fixed group G are conjugated, i.e., it is the problem to decide on input words x, y whether there exists z such that zxz- 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 BS1 , 2 and the Baumslag group G1 , 2 (also known as Baumslag–Gersten group). The conjugacy problem in BS1 , 2 is complete for the circuit class TC0. To the best of our knowledge BS1 , 2 is the first natural infinite non-commutative group where such a precise and low complexity is shown. The Baumslag group G1 , 2 is an HNN-extension of BS1 , 2. Hence, decidability of the conjugacy problem in G1 , 2 outside the so-called “black hole” follows from Borovik et al. (Int J Algebra Comput 17(5/6):963–997, 2007). Decidability everywhere is due to Beese. Moreover, he showed exponential time for the set of elements which cannot be conjugated into BS1 , 2 (Beese 2012). Here we improve Beese’s result in two directions by showing that the conjugacy problem in G1 , 2 can be solved in polynomial time in a strongly generic setting. This means that essentially for all inputs, conjugacy in G1 , 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 G1 , 2 by reducing the divisibility problem in power circuits to the conjugacy problem in G1 , 2. The complexity of the divisibility problem in power circuits is an open and interesting problem in integer arithmetic. We conjecture that it cannot be solved in elementary time because we can show that it cannot be solved in elementary time by calculating modulo values in power circuits.
KW - Algorithmic group theory
KW - Baumslag group
KW - Conjugacy problem
KW - Divisibility problem
KW - Generic case complexity
KW - Power circuit
UR - http://www.scopus.com/inward/record.url?scp=84954474163&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84954474163&partnerID=8YFLogxK
U2 - 10.1007/s00453-016-0117-z
DO - 10.1007/s00453-016-0117-z
M3 - Article
AN - SCOPUS:84954474163
SN - 0178-4617
VL - 76
SP - 961
EP - 988
JO - Algorithmica (New York)
JF - Algorithmica (New York)
IS - 4
ER -