{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:39:13Z","timestamp":1777516753984,"version":"3.51.4"},"reference-count":18,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2016,4,25]],"date-time":"2016-04-25T00:00:00Z","timestamp":1461542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>The conjugacy problem for a finitely generated group G is the two-variable problem of deciding for an arbitrary pair [Formula: see text] 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 [Formula: see text] of G, the problem of deciding if an arbitrary element is conjugate to [Formula: see text] 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 [Formula: see text]-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 \u201chalf-conjugacy\u201d problem to the conjugacy problem. In the last section we discuss the extreme opposite situation: groups with algorithmically finite conjugation.<\/jats:p>","DOI":"10.3233\/com-160060","type":"journal-article","created":{"date-parts":[[2017,10,31]],"date-time":"2017-10-31T12:01:45Z","timestamp":1509451305000},"page":"307-318","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":6,"title":["Computational complexity and the conjugacy problem"],"prefix":"10.1177","volume":"6","author":[{"given":"Alexei","family":"Miasnikov","sequence":"first","affiliation":[{"name":"Department of Mathematics, Stevens Institute of Technology, Hoboken, NJ 07030, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Schupp","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 West Green Street, Urbana, IL 61801, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2016,4,25]]},"reference":[{"key":"ref001","unstructured":"S.\u00a0Arora and B.\u00a0Borak, Computational Complexity: A Modern Approach, Cambridge University Press, Cambridge, UK, 2009."},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196707003652"},{"key":"ref003","first-page":"103","author":"Borovik A.V.","year":"2007","journal-title":"Vestnik OMGU"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196707003913"},{"key":"ref005","unstructured":"B.\u00a0Cavallo, J.\u00a0Delgado, D.\u00a0Kahrobei and E.\u00a0Ventura, Algorithmic recognition of infinite cyclic extensions, Preprint, arXiv:1509.05879 [math.GR]."},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392008"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392160"},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.1137\/050643295"},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-8693(03)00167-4"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2013-05898-9"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.1134\/S0001434615090060"},{"key":"ref012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61896-3"},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2011.03.019"},{"key":"ref014","unstructured":"C.F.\u00a0MillerIII, On Group-Theoretic Decision Problems and Their Classification, Ann. of Math. Studies, Vol.\u00a068, Princeton University Press, Princeton, 1971."},{"key":"ref015","doi-asserted-by":"crossref","unstructured":"C.F.\u00a0MillerIII, Decision problems for groups \u2013 Survey and reflections, in: Algorithms and Classification in Combinatorial Group Theory, G.\u00a0Baumslag and C.F.\u00a0MillerIII, eds, Springer, 1992, pp.\u00a01\u201360.","DOI":"10.1007\/978-1-4613-9730-4_1"},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.1090\/memo\/0804"},{"key":"ref017","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2010.172.1"},{"key":"ref018","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19650110210"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-160060","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-160060","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-160060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:59:54Z","timestamp":1777391994000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-160060"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,25]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.3233\/COM-160060"],"URL":"https:\/\/doi.org\/10.3233\/com-160060","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,25]]}}}