×

zbMATH — the first resource for mathematics

Hardness of embedding simplicial complexes in \(\mathbb R^d\). (English) Zbl 1208.68130
Summary: Let EMBED\(_{k \rightarrow 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 \(\mathbb R^d\)? Known results easily imply polynomiality of EMBED\(_{k \rightarrow 2}\) (\(k = 1, 2\); the case \(k = 1, d = 2\) is graph planarity) and of EMBED\(_{k\rightarrow 2k}\) for all \(k\geq 3\).
We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBED\(_{d \rightarrow d}\) and EMBED\(_{(d - 1)\rightarrow d}\) are undecidable for each \(d \geq 5\). Our main result is NP-hardness of EMBED\(_{2\rightarrow 4}\) and, more generally, of EMBED\(_{k\rightarrow d}\) for all \(k, d\) with \(d \geq 4\) and \(d \geq k \geq (2d - 2)/3\). These dimensions fall outside the metastable range of a theorem of Haefliger and Weber, which characterizes embeddability using the deleted product obstruction. Our reductions are based on examples, due to Segal, Spiez, Freedman, Krushkal, Teichner, and Skopenkov, showing that outside the metastable range, the deleted product obstruction is not sufficient to characterize embeddability.

MSC:
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
57Q35 Embeddings and immersions in PL-topology
PDF BibTeX Cite
Full Text: DOI
References:
[1] Acquistapace, F., Benedetti, R., Broglia, F.: Effectiveness-noneffectiveness in semi- algebraic and PL geometry. Invent. Math. 102, 141-156 (1990) · Zbl 0729.14040
[2] Agol, I., Hass, J., Thurston, W.: The computational complexity of knot genus and spanning area. Trans. Amer. Math. Soc. 358, 3821-3850 (2006) · Zbl 1098.57003
[3] Anick, D. J.: The computation of rational homotopy groups is #\?-hard. In: Computers in Geometry and Topology (Chicago, IL, 1986), Lecture Notes in Pure Appl. Math. 114, Deker, 1-56 (1989) · Zbl 0691.55009
[4] Arora, S., Barak, B.: Complexity Theory: A Modern Approach. Cambridge Univ. Press, Cambridge (2009); · Zbl 1193.68112
[5] Bing, R. H.: An alternative proof that 3-manifolds can be triangulated. Ann. of Math. (2) 69, 37-65 (1959) · Zbl 0106.16604
[6] Böhme, T.: On spatial representations of graphs. In: Contemporary Methods in Graph Theory, Bibliogr. Inst., Mannheim, 151-167 (1990) · Zbl 0718.05054
[7] Bokowski, J., Guedes de Oliveira, A.: On the generation of oriented matroids. Discrete Comput. Geom. 24, 197-208 (2000) · Zbl 0969.52008
[8] Brehm, U.: A nonpolyhedral triangulated Möbius strip. Proc. Amer. Math. Soc. 89, 519-522 (1983) · Zbl 0526.57013
[9] Brehm, U., Sarkaria, K. S.: Linear vs. piecewise linear embeddability of simplicial complexes. Tech. Report 92/52, Max-Planck-Institut f. Mathematik, Bonn (1992)
[10] Brown, E. H. (jun.): Finite computability of Postnikov complexes. Ann. of Math. (2) 65, 1-20 (1957) · Zbl 0077.16804
[11] Bryant, J. L.: Approximating embeddings of polyhedra in codimension three. Trans. Amer. Math. Soc. 170, 85-95 (1972) · Zbl 0259.57007
[12] Bryant, J. L.: Piecewise linear topology. In: R. J. Daverman et al. (eds.), Hand- book of Geometric Topology, Elsevier, Amsterdam, 219-259 (2002) · Zbl 0986.57021
[13] Buoncristiano, S.: Fragments of Geometric Topology from the Sixties. Geom. Topol. Monogr. 6 (2003). New edition in preparation, in collaboration with C. Rourke · Zbl 1066.57001
[14] Chojnacki (Hanani), C.: Über wesentlich unplättbare Kurven im dreidimensionalen Raume. Fund. Math. 23, 135-142 (1934) · Zbl 0009.41104
[15] Curtis, M. L., Zeeman, E. C.: On the polyhedral Schoenflies theorem. Proc. Amer. Math. Soc. 11, 888-889 (1961) · Zbl 0096.37903
[16] Dumas, J.-G., Saunders, B. D., Villard, G.: On efficient sparse integer matrix Smith normal form computations. J. Symbolic Comput. 32, 71-99 (2001) · Zbl 1050.65044
[17] Flores, A.: Über n-dimensionale Komplexe, die im R2n+1 absolut selbstverschlungen sind. Ergeb. Math. Kolloq. 6, 4-7 (1932/1934) · Zbl 0011.03804
[18] Freedman, M. H.: The topology of four-dimensional manifolds. J. Differential Geom. 17, 357-453 (1982) · Zbl 0528.57011
[19] Freedman, M. H., Krushkal, V. S., Teichner, P.: Van Kampen’s embedding obstruc- tion is incomplete for 2-complexes in 4 R . Math. Res. Lett. 1, 167-176 (1994) · Zbl 0847.57005
[20] Giesbrecht, M.: Fast computation of the Smith form of a sparse integer matrix. Comput. Complexity 10, 41-69 (2001) · Zbl 0992.65039
[21] Glaser, L. C.: A proof of the most general polyhedral Schoenflies conjecture possible. Pacific J. Math. 38, 401-417 (1971) · Zbl 0194.55604
[22] Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cam- bridge Univ. Press, Cambridge (2008); · Zbl 1154.68056
[23] Gonc\?alves, D., Skopenkov, A.: Embeddings of homology equivalent manifolds with boundary. Topology Appl. 153, 2026-2034 (2006) · Zbl 1105.57022
[24] Haefliger, A.: Plongements de variétés dans le domaine stable. In: Sém. Bourbaki 1962/63, fasc. 1, exp. 245 (1964) · Zbl 0127.13701
[25] Haken, W.: Theorie der Normalflächen. Acta Math. 105, 245-375 (1961) · Zbl 0100.19402
[26] Halin, R., Jung, H. A.: Charakterisierung der Komplexe der Ebene und der 2-Sphäre. Arch. Math. 15, 466-469 (1964) · Zbl 0125.11604
[27] Hass, J., Lagarias, J. C., Pippenger, N.: The computational complexity of knot and link problems. J. ACM 46, 185-211 (1999) · Zbl 1065.68667
[28] Hatcher, A.: Algebraic Topology. Cambridge Univ. Press, Cambridge (2001); · Zbl 1044.55001
[29] Hemion, G.: On the classification of homeomorphisms of 2-manifolds and the classification of 3-manifolds. Acta Math. 142, 123-155 (1979) · Zbl 0402.57027
[30] Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM 21, 549-568 (1974) · Zbl 0307.68025
[31] Ivanov, S. V.: The computational complexity of basic decision problems in 3-dimensional topology. Geom. Dedicata 131, 1-26 (2008) · Zbl 1146.57025
[32] Lickorish, W. B. R.: The piecewise linear unknotting of cones. Topology 4, 67-91 (1965) · Zbl 0138.19003
[33] Marde\check sić, S., Segal, J.: A note on polyhedra embeddable in the plane. Duke Math. J. 33, 633-638 (1966) · Zbl 0168.21602
[34] Marde\check sić, S., Segal, J.: \epsilon -mappings and generalized manifolds. Michigan Math. J. 14, 171-182 (1967) · Zbl 0152.21704
[35] Markov, A. A.: The insolubility of the problem of homeomorphy. Dokl. Akad. Nauk SSSR 121, 218-220 (1958) (in Russian) · Zbl 0092.00702
[36] Matou\check sek, J.: Using the Borsuk-Ulam Theorem. Springer, Berlin (2003) · Zbl 1016.05001
[37] Matveev, S. V.: Classification of sufficiently large 3-manifolds. Uspekhi Mat. Nauk 52, no. 5, 147-174 (1997) (in Russian); English transl.: Russian Math. Surveys 52, no. 5, 1029-1055 (1997) · Zbl 0916.57019
[38] Melikhov, S. A.: The van Kampen obstruction and its relatives. Tr. Mat. Inst. Steklova 266, 149-183 (2009) · Zbl 1196.57019
[39] Munkres, J. R.: Elements of Algebraic Topology. Addison-Wesley, Reading, MA (1984) · Zbl 0673.55001
[40] Nabutovsky, A.: Einstein structures: Existence versus uniqueness. Geom. Funct. Anal. 5, 76-91 (1995) · Zbl 0842.53032
[41] Nabutovsky, A., Weinberger, S.: Algorithmic unsolvability of the triviality problem for multidimensional knots. Comment. Math. Helv. 71, 426-434 (1996) · Zbl 0862.57017
[42] Nabutovsky, A., Weinberger, S.: Algorithmic aspects of homeomorphism problems. In: Tel Aviv Topology Conference: Rothenberg Festschrift (1998), Contemp. Math. 231, Amer. Math. Soc., Providence, RI, 245-250 (1999) · Zbl 0932.57021
[43] Newman, M. H. A.: On the division of Euclidean n-space by topological (n - 1)- spheres. Proc. Roy. Soc. London Ser. A 257, 1-12 (1960) · Zbl 0094.17601
[44] Papakyriakopoulos, C.: A new proof for the invariance of the homology groups of a complex. Bull. Soc. Math. Gr‘ece 22, 1-154 (1943) (in Greek)
[45] Renegar, J.: On the computational complexity and geometry of the first-order the- ory of the reals. I, II, III. J. Symbolic Comput. 13, 255-299, 301-327, 329-352 (1992) · Zbl 0798.68073
[46] Robertson, N., Seymour, P. D., Thomas, R.: A survey of linkless embeddings. In: Graph Structure Theory (Seattle, WA, 1991), Contemp. Math. 147, Amer. Math. Soc., Provi- dence, RI, 125-136 (1993) · Zbl 0788.05034
[47] Robertson, N., Seymour, P. D., Thomas, R.: Sachs’ linkless embedding conjecture. J. Combin. Theory Ser. B 64, 185-227 (1995) · Zbl 0832.05032
[48] Romero, A., Rubio, J., Sergeraert, F.: Computing spectral sequences. J. Symbolic Com- put. 41, 1059-1079 (2006) · Zbl 1132.55008
[49] Rourke, C. P., Sanderson, B. J.: Introduction to Piecewise-Linear Topology. Springer, Berlin (1982) · Zbl 0477.57003
[50] Rubinstein, J. H.: An algorithm to recognize the 3-sphere. In: Proc. Int. Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994), Birkhäuser, Basel, 601-611 (1995) · Zbl 0864.57009
[51] Schleimer, S.: Sphere recognition lies in NP. · Zbl 1250.57024
[52] Schön, R.: Effective algebraic topology. Mem. Amer. Math. Soc. 92, no. 451 (1991) · Zbl 0731.55015
[53] Segal, J., Skopenkov, A., Spie\?z, S.: Embeddings of polyhedra in m R and the deleted product obstruction. Topology Appl. 85, 335-344 (1998) · Zbl 0934.57025
[54] Segal, J., Spie\?z, S.: Quasi embeddings and embeddings of polyhedra in m R . Topology Appl. 45, 275-282 (1992) · Zbl 0768.57012
[55] Shapiro, A.: Obstructions to the imbedding of a complex in a euclidean space. I: The first obstruction. Ann. of Math. (2) 66, 256-269 (1957) · Zbl 0085.37701
[56] Skopenkov, A.: Embedding and knotting of manifolds in euclidean spaces. In: London Math. Soc. Lecture Note Ser. 347, 248-342 (2008) · Zbl 1154.57019
[57] Smith, J.: m-structures determine integral homotopy type. arXiv:math/9809151v1 (1998)
[58] Soare, R. I.: Computability theory and differential geometry. Bull. Symbolic Logic 10, 457-486 (2004) · Zbl 1085.03033
[59] Stallings, J.: Homology and central series of groups. J. Algebra 2, 170-181 (1965) · Zbl 0135.05201
[60] Steenrod, N. E.: Products of cocycles and extensions of mappings. Ann. of Math. (2) 48, 290-320 (1947) · Zbl 0030.41602
[61] Storjohann, A.: Near optimal algorithms for computing Smith normal forms of inte- ger matrices. In: International Symposium on Symbolic and Algebraic Computation (Zürich, 1996), ACM Press, New York, 267-274 (1996) · Zbl 0914.65043
[62] Thompson, A.: Thin position and the recognition problem for S3. Math. Res. Lett. 1, 613-630 (1994) · Zbl 0849.57009
[63] Tutte, W. T.: Toward a theory of crossing numbers. J. Combin. Theory 8, 45-53 (1970) · Zbl 0187.20803
[64] van Kampen, E. R.: Komplexe in euklidischen Räumen. Abh. Math. Sem. Hamburg 9, 72-78 (1932); Berichtigung, ibid., 152-153 · Zbl 0005.02604
[65] Volodin, I. A., Kuznetsov, V. E., Fomenko, A. T.: The problem of discriminating al- gorithmically the standard three-dimensional sphere. Uspekhi Mat. Nauk 29, no. 5, 71-168 (1974) (in Russian); English transl.: Russian Math. Surveys 29, no. 5, 71-172 (1974) · Zbl 0311.57001
[66] Weber, C.: Plongements de poly‘edres dans le domaine metastable. Comment. Math. Helv. 42, 1-27 (1967) · Zbl 0152.22402
[67] Wigderson, A.: P, NP and Mathematics-a computational complexity perspective. In: Proc. ICM 06 (Madrid), Vol. 1, Eur. Math. Soc. Publ. House, Zürich, 665-712 (2007); · Zbl 1149.68033
[68] Wu, W.-T.: A Theory of Imbedding, Immersion, and Isotopy of Polytopes in a Eu- clidean Space. Science Press, Peking (1965) · Zbl 0177.26402
[69] Ziegler, G. M.: Lectures on Polytopes. Springer, Berlin (1995) · Zbl 0823.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.