Embeddability in R^3 is NP-hard
| Autor: | Eric Sedgwick, Arnaud de Mesmay, Martin Tancer, Yo'av Rieck |
|---|---|
| Přispěvatelé: | GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Centre National de la Recherche Scientifique (CNRS), University of Arkansas [Fayetteville], School of Computing [DePaul] (SOC), DePaul University [Chicago], Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, de Mesmay, Arnaud, Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Department of Applied Mathematics [Prague] (KAM), Charles University [Prague] (CU) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Reduction (recursion theory)
Boundary (topology) 0102 computer and information sciences [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] 01 natural sciences Combinatorics Computational topology Simplicial complex Dehn surgery Artificial Intelligence [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT] 0101 mathematics Unknot Mathematics::Symplectic Geometry Time complexity ComputingMilieux_MISCELLANEOUS [MATH.MATH-GT] Mathematics [math]/Geometric Topology [math.GT] Mathematics 010102 general mathematics [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG] 010201 computation theory & mathematics Hardware and Architecture Control and Systems Engineering Computational problem Software Information Systems |
| Zdroj: | ACM-SIAM Symposium on Discrete Algorithms ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States Journal of the ACM (JACM) Journal of the ACM (JACM), Association for Computing Machinery, 2020, 67 (4), pp.1-29. ⟨10.1145/3396593⟩ |
| ISSN: | 0004-5411 1557-735X |
| Popis: | We prove that the problem of deciding whether a two- or three-dimensional simplicial complex embeds into R 3 is NP -hard. Our construction also shows that deciding whether a 3-manifold with boundary tori admits an S 3 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|