Embeddability in R 3 is NP-hard
- 4 June 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 67 (4), 1-29
- https://doi.org/10.1145/3396593
Abstract
We prove that the problem of deciding whether a two- or three-dimensional simplicial complex embeds into R3 is NP-hard. Our construction also shows that deciding whether a 3-manifold with boundary tori admits an S3 filling is NP-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 ∩ 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.Keywords
Funding Information
- Campus France (EMBEDS II CZ:7AMB17FR029 FR:38087RM)
- Agence Nationale de la Recherche (ANR-16-CE40-0009-01)
- Grantová Agentura ðeské Republiky (16-01602Y)
- Simons Foundation (637880)
This publication has 30 references indexed in Scilit:
- A TABLE OF GENUS TWO HANDLEBODY-KNOTS UP TO SIX CROSSINGSJournal of Knot Theory and Its Ramifications, 2012
- Hardness of embedding simplicial complexes in $\mathbb{R}^d$Journal of the European Mathematical Society, 2010
- Decision problems in the space of Dehn fillingsTopology, 2003
- The computational complexity of knot and link problemsJournal of the ACM, 1999
- Producing reducible 3-manifolds by surgery on a knotTopology, 1990
- Knots are determined by their complementsJournal of the American Mathematical Society, 1989
- Dehn Surgery on KnotsAnnals of Mathematics, 1987
- Incompressible planar surfaces in 3-manifoldsTopology and its Applications, 1984
- A Linear Time Planarity Algorithm for 2-ComplexesJournal of the ACM, 1979
- A Representation of Orientable Combinatorial 3-ManifoldsAnnals of Mathematics, 1962