Skopenkov's NP-hardness conjecture for geometric embeddability
Skopenkov's NP-hardness conjecture for geometric embeddability
For integers , let denote the decision problem of determining whether a given -complex has a geometric embedding in . Skopenkov's conjecture. The problem is NP-hard for all satisfying
Geometric embeddability is decidable for all 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 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.