Skopenkov's NP-hardness conjecture for geometric embeddability

About 5 years old · traced to

For integers k,dk,d, let GEM⁡k→d\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 GEM⁡k→d\operatorname{GEM}_{k \rightarrow d} is NP-hard for all k,dk,d satisfying

max⁡{3,k}≤d≤32k+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 GEM⁡2→3\operatorname{GEM}_{2 \rightarrow 3} as an interesting open problem.

References

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.