Embeddability in โ<sup>3</sup> is NP-hard
Embeddability in โ<sup>3</sup> is NP-hard
We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into โ3 is NP-hard. This stands in contrast with the lower dimensional cases which can be solved in linear time, and a variety of computational problems in โ3 like unknot or 3-sphere recognition which are โฆ