Hardness of embedding simplicial complexes in Rd

ABSTRACT

Let EMBED_k→d be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into R^d? Known results easily imply polynomiality of EMBED_k→2 (k = 1, 2; the case k = 1, d = 2 is graph planarity) and of EMBED_k→2k for all k ≥ 3 (even if k is not considered fixed).

We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBED_d→d and EMBED_(d-1)→d are undecidable for each d ≥ 5. Our main result is NP-hardness of EMBED_2→4 and, more generally, of EMBED_k→d for all k, d with d → 4 and d → k → (2d - 2)/3.

REFERENCES

• 1: I. Agol, J. Hass, and W. Thurston. The computational complexity of knot genus and spanning area. Trans. Am. Math. Soc., 358(9):3821--3850, 2006.
• 2: R. H. Bing. An alternative proof that 3-manifolds can be triangulated. Ann. Math. (2), 69:37--65, 1959.
• 3: T. Böhme. On spatial representations of graphs. In Contemporary methods in graph theory, pages 151--167. Bibliographisches Inst., Mannheim, 1990.
• 4: J. Bokowski and A. Guedes de Oliveira. On the generation of oriented matroids. Discrete Comput. Geom., 24(2--3):197--208, 2000. The Branko Grünbaum birthday issue.
• 5: U. Brehm. A nonpolyhedral triangulated Möbius strip. Proc. Amer. Math. Soc., 89(3):519--522, 1983.
• 6: U. Brehm and K. S. Sarkaria. Linear vs. piecewise linear embeddability of simplicial complexes. Tech. Report 92/52, Max-Planck-Institut f. Mathematik, Bonn, Germany, 1992.
• 7: E. H. Brown (jun.). Finite computability of Postnikov complexes. Ann. Math. (2), 65:1--20, 1957.
• 8: J. L. Bryant. Approximating embeddings of polyhedra in codimension three. Trans. Am. Math. Soc., 170:85--95, 1972.
• 9: J. L. Bryant. Piecewise linear topology. In Daverman, R. J. (ed.) et al., Handbook of geometric topology., pages 219--259. Elsevier, Amsterdam, 2002.
• 10: S. Buoncristiano. Fragments of Geometric Topology from the Sixties. Geometry & Topology Monographs, Vol. 6, 2003. New edition in preparation, in collaboration with C. Rourke.
• 11: A. Flores. Über n-dimensionale Komplexe, die im R_2n+1 absolut selbstverschlungen sind. Ergeb. Math. Kolloq., 6:4--7, 1932/1934.
• 12: M. H. Freedman, V. S. Krushkal, and P. Teichner. Van Kampen's embedding obstruction is incomplete for 2-complexes in R⁴. Math. Res. Lett., 1(2):167--176, 1994.
• 13: L. C. Glaser. A proof of the most general polyhedral Schoenflies conjecture possible. Pac. J. Math., 38:401--417, 1971.
• 14: W. Haken. Theorie der Normalflächen. Acta Math., 105:245--375, 1961.
• 15: R. Halin and H. A. Jung. Charakterisierung der Komplexe der Ebene und der 2-Sphäre. Arch. Math., 15:466--469, 1964.
• 16: Joel Hass , Jeffrey C. Lagarias , Nicholas Pippenger, The computational complexity of knot and link problems, Journal of the ACM (JACM), v.46 n.2, p.185-211, March 1999 [doi>10.1145/301970.301971]
• 17: A. Hatcher. Algebraic Topology. Cambridge University Press, Cambridge, 2001. Electronic version available at http://math.cornell.edu/hatcher#AT1.
• 18: G. Hemion. On the classification of homeomorphisms of 2-manifolds and the classification of 3-manifolds. Acta Math., 142(1--2):123--155, 1979.
• 19: S. V. Ivanov. The computational complexity of basic decision problems in 3-dimensional topology. Geom. Dedicata, 131:1--26, 2008.
• 20: S. Mardešić and J. Segal. A note on polyhedra embeddable in the plane. Duke Math. J., 33:633--638, 1966.
• 21: A. A. Markov. The insolubility of the problem of homeomorphy. Dokl. Akad. Nauk SSSR, 121:218--220, 1958.
• 22: J. Matoušek. Using the Borsuk--Ulam theorem. Springer, Berlin etc., 2003.
• 23: J. Matoušek, M. Tancer, and U. Wagner. Hardness of embedding simplicial complexes in R^d. Preprint, arXiv:0807.0336 {cs.CG}.
• 24: S. V. Matveev. Classification of sufficiently large 3-manifolds. Uspekhi Mat. Nauk, 52(5(317)):147--174, 1997. Translation in Russian Math. Surveys 52 (1997), no. 5, 1029--1055.
• 25: J. R. Munkres. Elements of Algebraic Topology. Addison-Wesley, Reading, MA, 1984.
• 26: A. Nabutovsky. Einstein structures: Existence versus uniqueness. Geom. Funct. Anal., 5(1):76--91, 1995.
• 27: A. Nabutovsky and S. Weinberger. Algorithmic unsolvability of the triviality problem for multidimensional knots. Comment. Math. Helv., 71(3):426--434, 1996.
• 28: A. Nabutovsky and S. Weinberger. Algorithmic aspects of homeomorphism problems. In Tel Aviv Topology Conference: Rothenberg Festschrift (1998), volume 231 of Contemp. Math., pages 245--250. Amer. Math. Soc., Providence, RI, 1999.
• 29: M. H. A. Newman. On the division of Euclidean n-space by topological (n - 1)-spheres. Proc. Roy. Soc. London Ser. A, 257:1--12, 1960.
• 30: C. Papakyriakopoulos. A new proof for the invariance of the homology groups of a complex (in Greek). Bull. Soc. Math. Grèce, 22:1--154 (1946), 1943.
• 31: James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Part III: quantifier elimination, Journal of Symbolic Computation, v.13 n.3, p.329-352, March 1992
• 32: N. Robertson, P. D. Seymour, and R. Thomas. A survey of linkless embeddings. In Graph structure theory (Seattle, WA, 1991), volume 147 of Contemp. Math., pages 125--136. Amer. Math. Soc., Providence, RI, 1993.
• 33: Neil Robertson , Paul Seymour , Robin Thomas, Sachs' linkless embedding conjecture, Journal of Combinatorial Theory Series B, v.64 n.2, p.185-227, July 1995 [doi>10.1006/jctb.1995.1032]
• 34: A. Romero, J. Rubio, and F. Sergeraert. Computing spectral sequences. J. Symb. Comput., 41(10):1059--1079, 2006. arXiv:cs/0602064.
• 35: C. P. Rourke and B. J. Sanderson. Introduction to piecewise-linear topology. Springer, Berlin, 1982. Rev. printing of "Ergebnisse der Mathematik und ihrer Grenzgebiete", Vol. 69, 1972.
• 36: J. H. Rubinstein. An algorithm to recognize the 3-sphere. In Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994), pages 601--611, Basel, 1995. Birkhäuser.
• 37: S. Schleimer. Sphere recognition lies in NP. Manuscript, available from http://www.warwick.ac.uk/~masgar, 2004.
• 38: R. Schön. Effective algebraic topology. Mem. Am. Math. Soc., 451:63 p., 1991.
• 39: J. Segal, A. Skopenkov, and S. Spież. Embeddings of polyhedra in R^m and the deleted product obstruction. Topology Appl., 85(1--3):335--344, 1998.
• 40: J. Segal and S. Spież. Quasi embeddings and embeddings of polyhedra in R^m. Topology Appl., 45(3):275--282, 1992.
• 41: A. Shapiro. Obstructions to the imbedding of a complex in a euclidean space. I: The first obstruction. Ann. of Math., II. Ser., 66:256--269, 1957.
• 42: J. Smith. m-structures determine integral homotopy type. Preprint, arXiv:math/9809151v1, 1998.
• 43: R. I. Soare. Computability theory and differential geometry. Bull. Symbolic Logic, 10(4):457--486, 2004.
• 44: A. Thompson. Thin position and the recognition problem for S³. Math. Res. Lett., 1(5):613--630, 1994.
• 45: R. E. van Kampen. Komplexe in euklidischen Räumen. Abh. Math. Sem. Hamburg, 9:72--78, 1932. Berichti-gung dazu, ibid. (1932) 152--153.
• 46: I. A. Volodin, V. E. Kuznetsov, and A. T. Fomenko. The problem of discriminating algorithmically the standard three-dimensional sphere. Usp. Mat. Nauk, 29(5):71--168, 1974. In Russian. English translation: Russ. Math. Surv. 29, 5:71--172 (1974).
• 47: W.-T. Wu. A Theory of Imbedding, Immersion, and Isotopy of Polytopes in a Euclidean Space. Science Press, Peking, 1965.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms