Skopenkov's NP-hardness conjecture for geometric embeddability

For integers k,dk,d, let GEMkd\operatorname{GEM}_{k \rightarrow d} denote the decision problem of determining whether a given kk-complex has a geometric embedding in Rd\mathbb{R}^d. Skopenkov's conjecture. The problem GEMkd\operatorname{GEM}_{k \rightarrow d} is NP-hard for all k,dk,d satisfying

max{3,k}d32k+1.\max\{3,k\} \leq d \leq \frac{3}{2}k+1.

Geometric embeddability is decidable for all k,dk,d because it can be expressed in the first-order theory of the reals. The conjectured NP-hardness extends the known complexity landscape for piecewise-linear embeddability, while the cited context identifies GEM23\operatorname{GEM}_{2 \rightarrow 3} as an interesting open problem.

Sources & referencesView supporting material

Primary source

Mikkel Abrahamsen, Linda Kleist and Tillmann Miltzow, “Geometric Embeddability of Complexes is R-complete”, arXiv:2108.02585 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.