@inproceedings{7806,
  abstract     = {We consider the following decision problem EMBEDk→d in computational topology (where k ≤ d are fixed positive integers): Given a finite simplicial complex K of dimension k, does there exist a (piecewise-linear) embedding of K into ℝd?
The special case EMBED1→2 is graph planarity, which is decidable in linear time, as shown by Hopcroft and Tarjan. In higher dimensions, EMBED2→3 and EMBED3→3 are known to be decidable (as well as NP-hard), and recent results of Čadek et al. in computational homotopy theory, in combination with the classical Haefliger–Weber theorem in geometric topology, imply that EMBEDk→d can be solved in polynomial time for any fixed pair (k, d) of dimensions in the so-called metastable range .
Here, by contrast, we prove that EMBEDk→d is algorithmically undecidable for almost all pairs of dimensions outside the metastable range, namely for . This almost completely resolves the decidability vs. undecidability of EMBEDk→d in higher dimensions and establishes a sharp dichotomy between polynomial-time solvability and undecidability.
Our result complements (and in a wide range of dimensions strengthens) earlier results of Matoušek, Tancer, and the second author, who showed that EMBEDk→d is undecidable for 4 ≤ k ϵ {d – 1, d}, and NP-hard for all remaining pairs (k, d) outside the metastable range and satisfying d ≥ 4.},
  author       = {Filakovský, Marek and Wagner, Uli and Zhechev, Stephan Y},
  booktitle    = {Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms},
  isbn         = {9781611975994},
  location     = {Salt Lake City, UT, United States},
  pages        = {767--785},
  publisher    = {SIAM},
  title        = {{Embeddability of simplicial complexes is undecidable}},
  doi          = {10.1137/1.9781611975994.47},
  volume       = {2020-January},
  year         = {2020},
}

@article{6563,
  abstract     = {This paper presents two algorithms. The first decides the existence of a pointed homotopy between given simplicial maps 𝑓,𝑔:𝑋→𝑌, and the second computes the group [𝛴𝑋,𝑌]∗ of pointed homotopy classes of maps from a suspension; in both cases, the target Y is assumed simply connected. More generally, these algorithms work relative to 𝐴⊆𝑋.},
  author       = {Filakovský, Marek and Vokřínek, Lukas},
  issn         = {16153383},
  journal      = {Foundations of Computational Mathematics},
  pages        = {311--330},
  publisher    = {Springer Nature},
  title        = {{Are two given maps homotopic? An algorithmic viewpoint}},
  doi          = {10.1007/s10208-019-09419-x},
  volume       = {20},
  year         = {2020},
}

@article{6774,
  abstract     = {A central problem of algebraic topology is to understand the homotopy groups  𝜋𝑑(𝑋)  of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group  𝜋1(𝑋)  of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with   𝜋1(𝑋)  trivial), compute the higher homotopy group   𝜋𝑑(𝑋)  for any given   𝑑≥2 . However, these algorithms come with a caveat: They compute the isomorphism type of   𝜋𝑑(𝑋) ,   𝑑≥2  as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of   𝜋𝑑(𝑋) . Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere   𝑆𝑑  to X has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space X, computes   𝜋𝑑(𝑋)  and represents its elements as simplicial maps from a suitable triangulation of the d-sphere   𝑆𝑑  to X. For fixed d, the algorithm runs in time exponential in   size(𝑋) , the number of simplices of X. Moreover, we prove that this is optimal: For every fixed   𝑑≥2 , we construct a family of simply connected spaces X such that for any simplicial map representing a generator of   𝜋𝑑(𝑋) , the size of the triangulation of   𝑆𝑑  on which the map is defined, is exponential in size(𝑋) .},
  author       = {Filakovský, Marek and Franek, Peter and Wagner, Uli and Zhechev, Stephan Y},
  issn         = {2367-1734},
  journal      = {Journal of Applied and Computational Topology},
  number       = {3-4},
  pages        = {177--231},
  publisher    = {Springer},
  title        = {{Computing simplicial representatives of homotopy group elements}},
  doi          = {10.1007/s41468-018-0021-5},
  volume       = {2},
  year         = {2018},
}