TY - JOUR
T1 - Generic complexity of the conjugacy problem in HNN-extensions and algorithmic stratification of Miller's groups
AU - Borovik, Alexandre V.
AU - Myasnikov, Alexei G.
AU - Remeslennikov, Vladimir N.
PY - 2007
Y1 - 2007
N2 - We discuss time complexity of the Conjugacy Problem in HNN-extensions of groups, in particular, in Miller's groups. We show that for "almost all", in some explicit sense, elements, the Conjugacy Problem is decidable in cubic time. It is worth noting that the Conjugacy Problem in a Miller group may be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group.
AB - We discuss time complexity of the Conjugacy Problem in HNN-extensions of groups, in particular, in Miller's groups. We show that for "almost all", in some explicit sense, elements, the Conjugacy Problem is decidable in cubic time. It is worth noting that the Conjugacy Problem in a Miller group may be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group.
KW - Algorithm
KW - Complexity
KW - Conjugation
KW - HNN-extension
UR - http://www.scopus.com/inward/record.url?scp=34748827928&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34748827928&partnerID=8YFLogxK
U2 - 10.1142/s0218196707003913
DO - 10.1142/s0218196707003913
M3 - Article
AN - SCOPUS:34748827928
SN - 0218-1967
VL - 17
SP - 963
EP - 967
JO - International Journal of Algebra and Computation
JF - International Journal of Algebra and Computation
IS - 5-6
ER -