Computational complexity and the conjugacy problem

Alexei Miasnikov, Paul Schupp

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

The conjugacy problem for a finitely generated group G is the two-variable problem of deciding for an arbitrary pair (u, v) of elements of G, whether or not u is conjugate to v in G. We construct examples of finitely generated, computably presented groups such that for every element u 0 of G, the problem of deciding if an arbitrary element is conjugate to u 0 is decidable in quadratic time but the worst-case complexity of the global conjugacy problem is arbitrary: it can be any c.e. Turing degree, can exactly mirror the Time Hierarchy Theorem, or can be NP-complete. Our groups also have the property that the conjugacy problem is generically linear time: that is, there is a linear time partial algorithm for the conjugacy problem whose domain has density 1, so hard instances are very rare. We also consider the complexity relationship of the half-conjugacy problem to the conjugacy problem. In the last section we discuss the extreme opposite situation: groups with algorithmically finite conjugation.

Original languageEnglish
Pages (from-to)307-318
Number of pages12
JournalComputability
Volume6
Issue number4
DOIs
StatePublished - 2017

Keywords

  • Conjugacy problem
  • NP-complete
  • algorithmically finite groups
  • decidability
  • half-conjugacy
  • individual conjugacy problem

Fingerprint

Dive into the research topics of 'Computational complexity and the conjugacy problem'. Together they form a unique fingerprint.

Cite this