{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:01:01Z","timestamp":1740178861895,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,9,6]],"date-time":"2021-09-06T00:00:00Z","timestamp":1630886400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,9,6]],"date-time":"2021-09-06T00:00:00Z","timestamp":1630886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Appl. and Comput. Topology"],"published-print":{"date-parts":[[2021,12]]},"DOI":"10.1007\/s41468-021-00076-0","type":"journal-article","created":{"date-parts":[[2021,9,6]],"date-time":"2021-09-06T08:04:38Z","timestamp":1630915478000},"page":"583-619","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the hardness of finding normal surfaces"],"prefix":"10.1007","volume":"5","author":[{"given":"Benjamin A.","family":"Burton","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2189-4942","authenticated-orcid":false,"given":"Alexander","family":"He","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,6]]},"reference":[{"key":"76_CR1","unstructured":"Agol, I.: Knot genus is NP. Conference presentation (2002)"},{"key":"76_CR2","unstructured":"Burton, B.A.: Minimal triangulations and normal surfaces. PhD thesis, The University of Melbourne (2003)"},{"key":"76_CR3","series-title":"Contemporary Mathematics","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1090\/conm\/597\/11877","volume-title":"Geometry and Topology Down Under","author":"BA Burton","year":"2013","unstructured":"Burton, B.A.: Computational topology with Regina: algorithms, heuristics and implementations. In: Geometry and Topology Down Under. Contemporary Mathematics, vol. 597, pp. 195\u2013224. American Mathematical Society, Providence (2013)"},{"issue":"1","key":"76_CR4","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/s00454-014-9572-y","volume":"52","author":"BA Burton","year":"2014","unstructured":"Burton, B.A.: A new approach to crushing 3-manifold triangulations. Discrete Comput. Geom. 52(1), 116\u2013139 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"76_CR5","unstructured":"Burton, B. A., Budney, R., Pettersson, W., et\u00a0al.: Regina: software for low-dimensional topology. https:\/\/regina-normal.github.io (1999\u20132017)"},{"key":"76_CR6","unstructured":"Burton B.A., \u00d6zlen, M.:A fast branching algorithm for unknot recognition with experimental polynomial\u2013time behaviour.Mathmatical programming (2012) in press"},{"key":"76_CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"key":"76_CR8","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/BF02559591","volume":"105","author":"W Haken","year":"1961","unstructured":"Haken, W.: Theorie der Normalfl\u00e4chen. Acta Math. 105, 245\u2013375 (1961)","journal-title":"Acta Math."},{"issue":"2","key":"76_CR9","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1145\/301970.301971","volume":"46","author":"J Hass","year":"1999","unstructured":"Hass, J., Lagarias, J.C., Pippenger, N.: The computational complexity of knot and link problems. J. ACM 46(2), 185\u2013211 (1999)","journal-title":"J. ACM"},{"issue":"1","key":"76_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10711-007-9210-4","volume":"131","author":"SV Ivanov","year":"2008","unstructured":"Ivanov, S.V.: The computational complexity of basic decision problems in 3-dimensional topology. Geom. Dedic. 131(1), 1\u201326 (2008)","journal-title":"Geom. Dedic."},{"issue":"2","key":"76_CR11","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0040-9383(84)90039-9","volume":"23","author":"W Jaco","year":"1984","unstructured":"Jaco, W., Oertel, U.: An algorithm to decide if a 3-manifold is a Haken manifold. Topology 23(2), 195\u2013299 (1984)","journal-title":"Topology"},{"issue":"1","key":"76_CR12","doi-asserted-by":"publisher","first-page":"61","DOI":"10.4310\/jdg\/1090503053","volume":"65","author":"W Jaco","year":"2003","unstructured":"Jaco, W., Rubinstein, J.H.: 0-efficient triangulations of 3-manifolds. J. Differ. Geom. 65(1), 61\u2013168 (2003)","journal-title":"J. Differ. Geom."},{"issue":"3","key":"76_CR13","first-page":"358","volume":"39","author":"W Jaco","year":"1995","unstructured":"Jaco, W., Tollefson, J.L.: Algorithms for the complete decomposition of a closed 3-manifold. Ill. J. Math. 39(3), 358\u2013406 (1995)","journal-title":"Ill. J. Math."},{"key":"76_CR14","unstructured":"Lackenby, M.: The efficient certification of knottedness and Thurston norm. arXiv Mathematics e-prints (2016). arXiv:1604.00290"},{"issue":"1","key":"76_CR15","doi-asserted-by":"publisher","first-page":"185","DOI":"10.2140\/pjm.1978.76.185","volume":"76","author":"JH Rubinstein","year":"1978","unstructured":"Rubinstein, J.H.: One-sided Heegaard splittings of 3-manifolds. Pac. J. Math. 76(1), 185\u2013200 (1978)","journal-title":"Pac. J. Math."},{"key":"76_CR16","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 216\u2013226. Association for Computing Machinery, New York (1978)","DOI":"10.1145\/800133.804350"},{"key":"76_CR17","doi-asserted-by":"crossref","unstructured":"Schleimer, S.: Sphere recognition lies in NP. In: Usher, M. (ed.) Low-Dimensional and Symplectic Topology. Proceedings of Symposia in Pure Mathematics, vol. 82, pp. 183\u2013213. American Mathematical Society (2011)","DOI":"10.1090\/pspum\/082\/2768660"},{"issue":"9","key":"76_CR18","doi-asserted-by":"publisher","first-page":"1643","DOI":"10.1215\/00127094-2018-0004","volume":"167","author":"R Zentner","year":"2018","unstructured":"Zentner, R.: Integer homology 3-spheres admit irreducible representations in $${\\rm SL}(2, {\\mathbb{C}})$$. Duke Math. J. 167(9), 1643\u20131712 (2018)","journal-title":"Duke Math. J."}],"container-title":["Journal of Applied and Computational Topology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-021-00076-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41468-021-00076-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-021-00076-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T20:40:47Z","timestamp":1635626447000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41468-021-00076-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,6]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["76"],"URL":"https:\/\/doi.org\/10.1007\/s41468-021-00076-0","relation":{},"ISSN":["2367-1726","2367-1734"],"issn-type":[{"type":"print","value":"2367-1726"},{"type":"electronic","value":"2367-1734"}],"subject":[],"published":{"date-parts":[[2021,9,6]]},"assertion":[{"value":"19 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 July 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}