From "Hardness of embedding simplicial complexes in $\mathbb{R}^d$," by Matoušek, Tancer, Wagner, 2009 (PDF download link):
According to a celebrated result of Novikov ([VKF74]; also see, e.g., [Nab95] for an exposition), the following problem is algorithmically unsolvable: Given a $d$-dimensional simplicial complex, $d \ge 5$, decide whether it is homeomorphic to $\mathbb{S}^d$, the $d$-dimensional sphere.
- [VKF74] I.A. Volodin, V.E. Kuznetsov, and A.T. Fomenko. The problem of discriminating algorithmically the standard three-dimensional sphere. Usp. Mat. Nauk, 29(5):71–168, 1974. In Russian. English translation: Russ. Math. Surv. 29,5:71–172 (1974).
- [Nab95] A. Nabutovsky. Einstein structures: Existence versus uniqueness. Geom. Funct. Anal., 5(1):76–91, 1995.
In their paper, they prove that deciding whether or not a finite simplicial complex $K$ of dimension at most $k$, can be (piecewise linearly) embedded into $\mathbb{R}^d$, is NP-hard, for all $k, d$ with $d \ge 4$ and $d \ge k \ge (2d− 2)/3$.
