Submission date: 2 May 2016

Abstract:

[Computability, to appear. DOI: 10.3233/COM-160060]
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.

Mathematics Subject Classification: 20F10 (Primary), 20F06 (Secondary)

Keywords and phrases:

Full text arXiv 1605.00598: pdf, ps.