TY - JOUR
T1 - Computational complexity and the conjugacy problem
AU - Miasnikov, Alexei
AU - Schupp, Paul
N1 - Publisher Copyright:
© 2017 - IOS Press and the authors. All rights reserved.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
KW - Conjugacy problem
KW - NP-complete
KW - algorithmically finite groups
KW - decidability
KW - half-conjugacy
KW - individual conjugacy problem
UR - http://www.scopus.com/inward/record.url?scp=85032699894&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85032699894&partnerID=8YFLogxK
U2 - 10.3233/COM-160060
DO - 10.3233/COM-160060
M3 - Article
AN - SCOPUS:85032699894
SN - 2211-3568
VL - 6
SP - 307
EP - 318
JO - Computability
JF - Computability
IS - 4
ER -