---
res:
bibo_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?\r\nThe
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
.\r\nHere, 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.\r\nOur 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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Marek
foaf_name: Filakovský, Marek
foaf_surname: Filakovský
foaf_workInfoHomepage: http://www.librecat.org/personId=3E8AF77E-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Uli
foaf_name: Wagner, Uli
foaf_surname: Wagner
foaf_workInfoHomepage: http://www.librecat.org/personId=36690CA2-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-1494-0568
- foaf_Person:
foaf_givenName: Stephan Y
foaf_name: Zhechev, Stephan Y
foaf_surname: Zhechev
foaf_workInfoHomepage: http://www.librecat.org/personId=3AA52972-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1137/1.9781611975994.47
bibo_volume: 2020-January
dct_date: 2020^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/9781611975994
dct_language: eng
dct_publisher: SIAM@
dct_title: Embeddability of simplicial complexes is undecidable@
...