Abstract
Let EMBEDkRIGHTWARDS ARROWd 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 R? Known results easily imply polynomiality of EMBEDkRIGHTWARDS ARROW2 (k = 1, 2; the case k = 1, d = 2 is graph planarity) and of EMBEDkRIGHTWARDS ARROW2k for all k GREATER-THAN OR EQUAL TO 3. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBEDdRIGHTWARDS ARROWd and EMBED(dMINUS SIGN 1)RIGHTWARDS ARROWd are undecidable for each d GREATER-THAN OR EQUAL TO 5.
Our main result is NP-hardness of EMBED2RIGHTWARDS ARROW4 and, more generally, of EMBEDkRIGHTWARDS ARROWd for all k, d with d GREATER-THAN OR EQUAL TO 4 and d GREATER-THAN OR EQUAL TO k GREATER-THAN OR EQUAL TO (2d MINUS SIGN 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 sufficient to characterize embeddability.