Conjugacy in baumslag's group, generic case complexity, and division in power circuiats

Volker Diekert, Alexei G. Myasnikov, Armin Weiß

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

12 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationLATIN 2014
Subtitle of host publicationTheoretical Informatics - 11th Latin American Symposium, Proceedings
Pages1-12
Number of pages12
DOIs
StatePublished - 2014
Event11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Uruguay
Duration: 31 Mar 20144 Apr 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8392 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th Latin American Theoretical Informatics Symposium, LATIN 2014
Country/TerritoryUruguay
CityMontevideo
Period31/03/144/04/14

Keywords

  • Algorithmic group theory
  • generic case complexity
  • power circuit

Fingerprint

Dive into the research topics of 'Conjugacy in baumslag's group, generic case complexity, and division in power circuiats'. Together they form a unique fingerprint.

Cite this