The conjugacy problem for a finitely generated group G is the two-variable problem of deciding for an arbitrary pair 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 of G, the problem of deciding if an arbitrary element is conjugate to 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 -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.
S.Arora and B.Borak, Computational Complexity: A Modern Approach, Cambridge University Press, Cambridge, UK, 2009.
2.
A.V.Borovik, A.G.Myasnikov and V.N.Remeslennikov, The conjugacy problem in amalgamated products I: Regular elements and black holes, Int. J. of Algebra. and Comp.17 (2007), 1299–1333.
3.
A.V.Borovik, A.G.Myasnikov and V.N.Remeslennikov, The conjugacy problem in HNN-extensions I: Regular elements, black holes and generic complexity, Vestnik OMGU (2007), 103–110, Special Issue, see also Preprint, arXiv:0903.3751[math.GR].
4.
A.V.Borovik, A.G.Myasnikov and V.N.Remeslennikov, Algorithmic stratification of the conjugacy problem in Miller’s groups, International Journal of Algebra and Computation17 (2007), 963–997.
5.
B.Cavallo, J.Delgado, D.Kahrobei and E.Ventura, Algorithmic recognition of infinite cyclic extensions, Preprint, arXiv:1509.05879 [math.GR].
6.
D.J.Collins, Recursively enumerable degrees and the conjugacy problem, Acta Mathematica125 (1969), 115–160.
7.
D.J.Collins, Representations of Turing reducibility by word and conjugacy problems in finitely presented groups, Acta Mathematica1(28) (1972), 73–90.
8.
Y.Gurevich and P.Schupp, The uniform membership problem for the modular group, SIAM Journal on Computing37 (2007), 425–459.
9.
I.Kapovich, A.G.Miasnikov, P.E.Schupp and V.Shpilrain, Generic-case complexity, decision problems in group theory and random walks, J. Algebra264 (2003), 665–694.
10.
B.Khoussainov and A.Myasnikov, Finitely presented expansions of groups, semigroups and algebras, Trans. AMS.366(3) (2014), 1455–1474.
11.
A.Klyachko and A.Mongush, Residually finite algorithmically finite groups, their subgroups and direct products, 2014, arXiv:1402.0887 [math.GR].
12.
R.C.Lyndon and P.E.Schupp, Combinatorial Group Theory, Ergebnisse der Mathematik, Vol. 89, Springer-Verlag, 1977. (Reprinted in the Springer Classics in Mathematics series, 2000.)
13.
A.Miasnikov and D.Osin, Algorithmically finite groups, Journal of Pure and Applied Algebra215 (2011), 2789–2796.
14.
C.F.MillerIII, On Group-Theoretic Decision Problems and Their Classification, Ann. of Math. Studies, Vol. 68, Princeton University Press, Princeton, 1971.
15.
C.F.MillerIII, Decision problems for groups – Survey and reflections, in: Algorithms and Classification in Combinatorial Group Theory, G.Baumslag and C.F.MillerIII, eds, Springer, 1992, pp. 1–60.
16.
A.Ol’shanskii and M.Sapir, The Conjugacy Problem and Higman Embeddings, Memoirs of the Amer. Math. Soc., Vol. 804, 2004.
17.
D.Osin, Small cancellation over relatively hyperbolic groups and embedding theorems, Annals of Math172 (2010), 1–39.
18.
J.C.Shepherdson, Machine configuration and word problems of given degree of unsolvability, Zeit. f. Math. Logik und Grundlagen der Math.24 (1965), 149–175.
