Computational complexity and the conjugacy problem

الأصل · EN

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₀ of G, the problem of deciding if an arbitrary element is conjugate to u₀ 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.