{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:13:23Z","timestamp":1778498003529,"version":"3.51.4"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T00:00:00Z","timestamp":1591228800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006537","name":"Campus France","doi-asserted-by":"publisher","award":["EMBEDS II CZ:7AMB17FR029 FR:38087RM"],"award-info":[{"award-number":["EMBEDS II CZ:7AMB17FR029 FR:38087RM"]}],"id":[{"id":"10.13039\/501100006537","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005304","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE40-0009-01"],"award-info":[{"award-number":["ANR-16-CE40-0009-01"]}],"id":[{"id":"10.13039\/501100005304","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Grantov\u00e1 Agentura \u00f0esk\u00e9 Republiky","award":["16-01602Y"],"award-info":[{"award-number":["16-01602Y"]}]},{"DOI":"10.13039\/100014155","name":"Simons Foundation","doi-asserted-by":"publisher","award":["637880"],"award-info":[{"award-number":["637880"]}],"id":[{"id":"10.13039\/100014155","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>\n            We prove that the problem of deciding whether a two- or three-dimensional simplicial complex embeds into R\n            <jats:sup>3<\/jats:sup>\n            is\n            <jats:bold>NP<\/jats:bold>\n            -hard. Our construction also shows that deciding whether a 3-manifold with boundary tori admits an S\n            <jats:sup>3<\/jats:sup>\n            filling is\n            <jats:bold>NP<\/jats:bold>\n            -hard. The former stands in contrast with the lower-dimensional cases, which can be solved in linear time, and the latter with a variety of computational problems in 3-manifold topology, for example, unknot or 3-sphere recognition, which are in NP \u2229 co- NP. (Membership of the latter problem in co-NP assumes the Generalized Riemann Hypotheses.) Our reduction encodes a satisfiability instance into the embeddability problem of a 3-manifold with boundary tori, and relies extensively on techniques from low-dimensional topology, most importantly Dehn fillings of manifolds with boundary tori.\n          <\/jats:p>","DOI":"10.1145\/3396593","type":"journal-article","created":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T10:06:01Z","timestamp":1591265161000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Embeddability in R\n            <sup>3<\/sup>\n            is NP-hard"],"prefix":"10.1145","volume":"67","author":[{"given":"Arnaud de","family":"Mesmay","sequence":"first","affiliation":[{"name":"LIGM, Univ Gustave Eiffel, CNRS, ESIEE Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yo\u2019av","family":"Rieck","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, University of Arkansas, Fayetteville, AR, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Sedgwick","sequence":"additional","affiliation":[{"name":"School of Computing, DePaul University, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Tancer","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, Charles University, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-05-03919-X"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_1_3_1","volume-title":"A Journey Through Discrete Mathematics: A Tribute to Ji\u0159\u00ed Matou\u0161ek, Martin Loebl, Jaroslav Ne\u0161et\u0159il","author":"Bachman David"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2140\/gt.2016.20.1061"},{"key":"e_1_2_1_5_1","volume-title":"Finding non-orientable surfaces in 3-manifolds. Discrete 8 Computational Geometry 58, 4 (1","author":"Burton Benjamin A.","year":"2017"},{"key":"e_1_2_1_6_1","volume-title":"Burton and Jonathan Spreer","author":"Benjamin","year":"2013"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597629"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9855-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/120899029"},{"key":"e_1_2_1_10_1","volume-title":"Shalen","author":"Culler Marc","year":"1987"},{"key":"e_1_2_1_11_1","unstructured":"Ralph H. Fox. 1948. On the imbedding of polyhedra in 3-space. Ann. Math. (1948) 462--470.  Ralph H. Fox. 1948. On the imbedding of polyhedra in 3-space. Ann. Math. (1948) 462--470."},{"key":"e_1_2_1_12_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1990"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-8641(84)90005-1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1989-0965210-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322156"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301971"},{"key":"e_1_2_1_17_1","unstructured":"Allen Hatcher. 2002. Algebraic Topology. Cambridge University Press.  Allen Hatcher. 2002. Algebraic Topology. Cambridge University Press."},{"key":"e_1_2_1_18_1","unstructured":"Allen Hatcher. 2007. Notes on basic 3-manifold topology. Retrieved from http:\/\/pi.math.cornell.edu\/ hatcher\/.  Allen Hatcher. 2007. Notes on basic 3-manifold topology. Retrieved from http:\/\/pi.math.cornell.edu\/ hatcher\/."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218216511009893"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2969\/jmsj\/06710407"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1258138058"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/043"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0040-9383(02)00083-6"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01406222"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-013-9159-7"},{"key":"e_1_2_1_26_1","unstructured":"Greg Kuperberg. 2015. Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization. (2015). arXiv:1508.06720.  Greg Kuperberg. 2015. Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization. (2015). arXiv:1508.06720."},{"key":"e_1_2_1_27_1","unstructured":"Marc Lackenby. 2016. The efficient certification of knottedness and Thurston norm. (2016). arXiv:1604.00290.  Marc Lackenby. 2016. The efficient certification of knottedness and Thurston norm. (2016). arXiv:1604.00290."},{"key":"e_1_2_1_28_1","volume-title":"Some conditionally hard problems on links and 3-manifolds. Discrete Comput. Geom. 58, 3 (01","author":"Lackenby Marc","year":"2017"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2307\/1970373"},{"key":"e_1_2_1_30_1","volume-title":"An Introduction to Knot Theory. Graduate Texts in Mathematics","author":"Raymond Lickorish W. B."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","volume-title":"Using the Borsuk-Ulam theorem","author":"Matou\u0161ek Ji\u0159\u00ed","DOI":"10.1007\/978-3-540-76649-0"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078632"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/252"},{"key":"e_1_2_1_34_1","volume-title":"Algorithmic Topology and Classification of 3-manifolds. Algorithms and Computation in Mathematics","author":"Matveev Sergei V."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018","author":"de Mesmay Arnaud","year":"2018"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","volume-title":"Elements of Algebraic Topology","author":"Munkres James R.","DOI":"10.1201\/9780429493911"},{"key":"e_1_2_1_37_1","volume-title":"Handbook of Graph Drawing and Visualization","author":"Patrignani Maurizio"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.2140\/agt.2016.16.3445"},{"key":"e_1_2_1_39_1","volume-title":"Mathematics Lecture Series","volume":"7","author":"Rolfsen Dale","year":"1990"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0040-9383(90)90017-E"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-04-07704-4"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","volume-title":"Sphere recognition lies in NP","author":"Schleimer Saul","DOI":"10.1090\/pspum\/082\/2768660"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","volume-title":"Introduction to 3-manifolds","author":"Schultens Jennifer","DOI":"10.1090\/gsm\/151"},{"key":"e_1_2_1_44_1","first-page":"93","article-title":"On surfaces in 3-space","volume":"18","author":"Tsukui Yasuyuki","year":"1970","journal-title":"Yokohama Math. J."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1215\/00127094-2018-0004"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3396593","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3396593","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:28Z","timestamp":1750199608000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3396593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,4]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3396593"],"URL":"https:\/\/doi.org\/10.1145\/3396593","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,4]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}