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

Volker Diekert, Alexei G. Myasnikov, Armin Weiß

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)961-988
Number of pages28
JournalAlgorithmica (New York)
Volume76
Issue number4
DOIs
StatePublished - 1 Dec 2016

Keywords

  • Algorithmic group theory
  • Baumslag group
  • Conjugacy problem
  • Divisibility problem
  • Generic case complexity
  • Power circuit

Fingerprint

Dive into the research topics of 'Conjugacy in Baumslag’s Group, Generic Case Complexity, and Division in Power Circuits'. Together they form a unique fingerprint.

Cite this