{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T13:08:34Z","timestamp":1648991314271},"reference-count":24,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2019,3]]},"abstract":" Agol, Haas and Thurston showed that the problem of determining a bound on the genus of a knot in a 3-manifold, is NP-complete. This shows that (unless P[Formula: see text]NP) the genus problem has high computational complexity even for knots in a 3-manifold. We initiate the study of classes of knots where the genus problem and even the equivalence problem have very low computational complexity. We show that the genus problem for alternating knots with n crossings has linear time complexity and is in Logspace[Formula: see text]. Alternating knots with some additional combinatorial structure will be referred to as standard. As expected, almost all alternating knots of a given genus are standard. We show that the genus problem for these knots belongs to [Formula: see text] circuit complexity class. We also show, that the equivalence problem for such knots with [Formula: see text] crossings has time complexity [Formula: see text] and is in Logspace[Formula: see text] and [Formula: see text] complexity classes. <\/jats:p>","DOI":"10.1142\/s0218196718500698","type":"journal-article","created":{"date-parts":[[2018,9,20]],"date-time":"2018-09-20T03:16:06Z","timestamp":1537413366000},"page":"245-262","source":"Crossref","is-referenced-by-count":0,"title":["Low complexity algorithms in knot theory"],"prefix":"10.1142","volume":"29","author":[{"given":"Olga","family":"Kharlampovich","sequence":"first","affiliation":[{"name":"Department of Math and Stats Hunter, College and Graduate Center CUNY, New York, USA"}]},{"given":"Alina","family":"Vdovina","sequence":"additional","affiliation":[{"name":"School of Math, Stats and Physics, Newcastle University, UK"}]}],"member":"219","published-online":{"date-parts":[[2019,4,2]]},"reference":[{"key":"S0218196718500698BIB001","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-05-03919-X"},{"key":"S0218196718500698BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00249-7"},{"key":"S0218196718500698BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0040-9383(95)93237-2"},{"key":"S0218196718500698BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196130"},{"key":"S0218196718500698BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90018-6"},{"key":"S0218196718500698BIB006","first-page":"329","volume-title":"Computational Problems in Abstract Algebra","author":"Conway J. H.","year":"1969"},{"key":"S0218196718500698BIB007","doi-asserted-by":"publisher","DOI":"10.2307\/1970181"},{"key":"S0218196718500698BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/BF01455155"},{"key":"S0218196718500698BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/BF02559591"},{"key":"S0218196718500698BIB010","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301971"},{"key":"S0218196718500698BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/0040-9383(87)90009-7"},{"issue":"2","key":"S0218196718500698BIB012","first-page":"323","volume":"6","author":"Knuth D.","year":"1977","journal-title":"J. Comput."},{"key":"S0218196718500698BIB013","series-title":"Clay Lecture Notes","volume-title":"Lectures on Geometry","author":"Lackenby M.","year":"2017"},{"key":"S0218196718500698BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/BF01117471"},{"key":"S0218196718500698BIB015","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1991-16083-0"},{"key":"S0218196718500698BIB016","doi-asserted-by":"publisher","DOI":"10.2969\/jmsj\/01030235"},{"key":"S0218196718500698BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/0040-9383(87)90058-9"},{"key":"S0218196718500698BIB018","doi-asserted-by":"publisher","DOI":"10.1155\/S1073792894000486"},{"key":"S0218196718500698BIB019","series-title":"Mathematical Lecture Series 7","volume-title":"Knots and Links","author":"Rolfsen D.","year":"1976"},{"key":"S0218196718500698BIB020","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-01-05823-3"},{"key":"S0218196718500698BIB021","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021211008278"},{"key":"S0218196718500698BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-005-0659-x"},{"key":"S0218196718500698BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/0040-9383(87)90003-6"},{"key":"S0218196718500698BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(72)90056-1"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196718500698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T15:24:36Z","timestamp":1565105076000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196718500698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3]]},"references-count":24,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2019,4,2]]},"published-print":{"date-parts":[[2019,3]]}},"alternative-id":["10.1142\/S0218196718500698"],"URL":"https:\/\/doi.org\/10.1142\/s0218196718500698","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3]]}}}