Hardness of embedding simplicial complexes in \(\mathbb R^d\) (Q621847)

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.