TY - GEN
T1 - Conjugacy in baumslag's group, generic case complexity, and division in power circuiats
AU - Diekert, Volker
AU - Myasnikov, Alexei G.
AU - Weiß, Armin
PY - 2014
Y1 - 2014
N2 - 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 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 BS 1,2 and the Baumslag(-Gersten) group G1,2. The conjugacy problem in BS1,2 is TC0-complete. 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 and its conjugacy problem is decidable G 1,2 by a result of Beese (2012). Here we show that conjugacy 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 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.
AB - 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 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 BS 1,2 and the Baumslag(-Gersten) group G1,2. The conjugacy problem in BS1,2 is TC0-complete. 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 and its conjugacy problem is decidable G 1,2 by a result of Beese (2012). Here we show that conjugacy 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 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.
KW - Algorithmic group theory
KW - generic case complexity
KW - power circuit
UR - http://www.scopus.com/inward/record.url?scp=84899991143&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84899991143&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-54423-1_1
DO - 10.1007/978-3-642-54423-1_1
M3 - Conference contribution
AN - SCOPUS:84899991143
SN - 9783642544224
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 12
BT - LATIN 2014
T2 - 11th Latin American Theoretical Informatics Symposium, LATIN 2014
Y2 - 31 March 2014 through 4 April 2014
ER -