Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

The conjugacy problem for groups of alternating prime tame links is polynomial-time


Author: Karin Johnsgard
Journal: Trans. Amer. Math. Soc. 349 (1997), 857-901
MSC (1991): Primary 20F10, 03D15, 57M25
MathSciNet review: 1351491
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: An alternating projection of a prime link can to used to produce a group presentation (of the link group under free product with the infinite cyclic group) with some useful peculiarities, including small cancellation conditions. In this presentation, conjugacy diagrams are shown to have the form of a tiling of squares in the Euclidean plane in one of a limited number of shapes. An argument based on the shape of the link projection is used to show that the tiling requires no more square tiles than a linear function of word length (with constant multiple based on the number of link crossings). It follows that the computation time for testing conjugacy of two group elements (previously known to be no worse than exponential) is bounded by a cubic polynomial. This bounds complexity in the original link group.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 20F10, 03D15, 57M25

Retrieve articles in all journals with MSC (1991): 20F10, 03D15, 57M25


Additional Information

Karin Johnsgard
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Email: karinj@math.cornell.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-97-01617-6
PII: S 0002-9947(97)01617-6
Received by editor(s): May 26, 1994
Received by editor(s) in revised form: September 11, 1995
Additional Notes: The author was supported in part by Alfred P. Sloan Dissertation Fellowship Grant #DD-414.
Article copyright: © Copyright 1997 American Mathematical Society