# Hardness of embedding simplicial complexes in ℝ<sup><em>d</em></sup>

### Jiří Matoušek

Charles University, Praha, Czech Republic### Martin Tancer

Charles University, Praha 1, Czech Republic### Uli Wagner

ETH Zentrum, Zürich, Switzerland

## Abstract

Let EMBEDk→d be the following algorithmic problem: Given a ﬁnite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into ℝd? Known results easily imply polynomiality of EMBEDk→2 (k = 1, 2; the case k = 1, d = 2 is graph planarity) and of EMBEDk→2k for all k ≥ 3. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBEDd→d and EMBED(d−1)→d are undecidable for each d ≥ 5. Our main result is NP-hardness of EMBED2→4 and, more generally, of EMBEDk→d for all k, d with d ≥ 4 and d ≥ k ≥ (2d − 2)/3. These dimensions fall outside the *metastable range* of a theorem of Haeﬂiger 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 suﬃcient to characterize embeddability.

## Cite this article

Jiří Matoušek, Martin Tancer, Uli Wagner, Hardness of embedding simplicial complexes in ℝ<sup><em>d</em></sup>. J. Eur. Math. Soc. 13 (2011), no. 2, pp. 259–295

DOI 10.4171/JEMS/252