Hardness of embedding simplicial complexes in ${ℝ}^d$

Matoušek, Jiří, Tancer, Martin, and Wagner, Uli. "Hardness of embedding simplicial complexes in $\mathbb {R}^d$." Journal of the European Mathematical Society 013.2 (2011): 259-295. <http://eudml.org/doc/277789>.

@article{Matoušek2011,
abstract = {Let $\texttt \{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 $\texttt \{EMBED\}_\{k\rightarrow 2\}$ ($k = 1, 2$; the case $k = 1, d = 2$ is graph planarity) and of $\texttt \{EMBED\}_\{k\rightarrow 2k\}$ for all $k\ge 3$. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that $\texttt \{EMBED\}_\{d\rightarrow d\}$ and $\texttt \{EMBED\}_\{(d-1)\rightarrow d\}$ are undecidable for each $_d\ge 5$. Our main result is NP-hardness of $\texttt \{EMBED\}_\{2\rightarrow 4\}$ and, more generally, of $\texttt \{EMBED\}_\{k\rightarrow d\}$ for all $k$, $d$ with $d\ge 4$ and $d\ge k \ge (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 outz side the metastable range the deleted product obstruction is not suffcient to characterize embeddability.},
author = {Matoušek, Jiří, Tancer, Martin, Wagner, Uli},
journal = {Journal of the European Mathematical Society},
keywords = {algorithmic unsolvability; finite simplicial complex; (piecewise linear) embeddability; NP-hard; algorithmic unsolvability; finite simplicial complex; (piecewise linear) embeddability; NP-hard},
language = {eng},
number = {2},
pages = {259-295},
publisher = {European Mathematical Society Publishing House},
title = {Hardness of embedding simplicial complexes in $\mathbb \{R\}^d$},
url = {http://eudml.org/doc/277789},
volume = {013},
year = {2011},
}

TY - JOUR
AU - Matoušek, Jiří
AU - Tancer, Martin
AU - Wagner, Uli
TI - Hardness of embedding simplicial complexes in $\mathbb {R}^d$
JO - Journal of the European Mathematical Society
PY - 2011
PB - European Mathematical Society Publishing House
VL - 013
IS - 2
SP - 259
EP - 295
AB - Let $\texttt {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 $\texttt {EMBED}_{k\rightarrow 2}$ ($k = 1, 2$; the case $k = 1, d = 2$ is graph planarity) and of $\texttt {EMBED}_{k\rightarrow 2k}$ for all $k\ge 3$. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that $\texttt {EMBED}_{d\rightarrow d}$ and $\texttt {EMBED}_{(d-1)\rightarrow d}$ are undecidable for each $_d\ge 5$. Our main result is NP-hardness of $\texttt {EMBED}_{2\rightarrow 4}$ and, more generally, of $\texttt {EMBED}_{k\rightarrow d}$ for all $k$, $d$ with $d\ge 4$ and $d\ge k \ge (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 outz side the metastable range the deleted product obstruction is not suffcient to characterize embeddability.
LA - eng
KW - algorithmic unsolvability; finite simplicial complex; (piecewise linear) embeddability; NP-hard; algorithmic unsolvability; finite simplicial complex; (piecewise linear) embeddability; NP-hard
UR - http://eudml.org/doc/277789
ER -