{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T04:01:39Z","timestamp":1742961699071,"version":"3.40.3"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"name":"the National Science Foundation","award":["DMS-2348792"],"award-info":[{"award-number":["DMS-2348792"]}]},{"name":"the National Science Foundation","award":["DMS-2153823\/DMS-2419591"],"award-info":[{"award-number":["DMS-2153823\/DMS-2419591"]}]},{"name":"the National Science Foundation","award":["DMS-2054558"],"award-info":[{"award-number":["DMS-2054558"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:p> In this paper, we answer two questions on the complexities of decision problems of groups, each related to a classical result. First, Miller characterized the complexity of the isomorphism problem for finitely presented groups in 1971. We do the same for the isomorphism problem for recursively presented groups. Second, the fact that every Turing degree appears as the degree of the word problem of a finitely presented group is shown independently by multiple people in the 1960s. We answer the analogous question for degrees of ceers instead of Turing degrees. We show that the set of ceers which are computably equivalent to the word problem of a finitely presented group is [Formula: see text]-complete, which is the maximal possible complexity. <\/jats:p>","DOI":"10.1142\/s0218196725500067","type":"journal-article","created":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T04:50:26Z","timestamp":1737175826000},"page":"311-327","source":"Crossref","is-referenced-by-count":0,"title":["Two results on complexities of decision problems of groups"],"prefix":"10.1142","volume":"35","author":[{"given":"Uri","family":"Andrews","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Wisconsin - Madison, 480 Lincoln Drive Madison, WI 53706 United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Harrison-Trainor","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Statistics, and Computer Science University of Illinois Chicago, 851 S.\u00a0Morgan Street Chicago, IL 60607 United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6292-6835","authenticated-orcid":false,"given":"Meng-Che \u201cTurbo\u201d","family":"Ho","sequence":"additional","affiliation":[{"name":"Department of Mathematics California State University, Northridge 18111 Nordhoff Street Northridge, CA 91330, United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2025,3,10]]},"reference":[{"key":"S0218196725500067BIB001","first-page":"533","volume":"103","author":"Adyan S. I.","year":"1955","journal-title":"Dokl. Akad. Nauk SSSR (N.S.)"},{"key":"S0218196725500067BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-50062-1_25"},{"key":"S0218196725500067BIB003","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2013.8"},{"key":"S0218196725500067BIB005","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2016.26"},{"key":"S0218196725500067BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2017.12.001"},{"key":"S0218196725500067BIB007","doi-asserted-by":"publisher","DOI":"10.3233\/COM-180098"},{"issue":"1","key":"S0218196725500067BIB008","first-page":"15","volume":"6","author":"Bokut L. A.","year":"1967","journal-title":"Algebra Logika Sem."},{"key":"S0218196725500067BIB010","doi-asserted-by":"publisher","DOI":"10.2307\/1970530"},{"key":"S0218196725500067BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"S0218196725500067BIB012","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-14.4.633"},{"key":"S0218196725500067BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456932"},{"key":"S0218196725500067BIB014","first-page":"620","volume":"10","author":"Er\u0161ov J. L.","year":"1971","journal-title":"Algebra Logika"},{"key":"S0218196725500067BIB015","first-page":"805","volume":"147","author":"Fridman A. A.","year":"1962","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"S0218196725500067BIB016","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010521410739"},{"key":"S0218196725500067BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2020.102855"},{"key":"S0218196725500067BIB018","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1961.0132"},{"key":"S0218196725500067BIB019","series-title":"Annals of Mathematics Studies","volume-title":"On Group-Theoretic Decision Problems and Their Classification","volume":"68","author":"Miller C. F.","year":"1971"},{"key":"S0218196725500067BIB020","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129516000335"},{"key":"S0218196725500067BIB022","doi-asserted-by":"publisher","DOI":"10.2307\/1969933"},{"key":"S0218196725500067BIB023","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196723500339"},{"key":"S0218196725500067BIB024","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.1998.7825"},{"key":"S0218196725500067BIB025","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19760220122"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196725500067","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T03:28:54Z","timestamp":1742873334000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218196725500067"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3]]},"references-count":22,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10.1142\/S0218196725500067"],"URL":"https:\/\/doi.org\/10.1142\/s0218196725500067","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"type":"print","value":"0218-1967"},{"type":"electronic","value":"1793-6500"}],"subject":[],"published":{"date-parts":[[2025,3]]}}}