Current browse context:
cs.CC
Change to browse by:
References & Citations
Computer Science > Computational Complexity
Title: Geometric Embeddability of Complexes is $\exists \mathbb R$-complete
(Submitted on 5 Aug 2021 (v1), last revised 5 Nov 2021 (this version, v2))
Abstract: We show that the decision problem of determining whether a given (abstract simplicial) $k$-complex has a geometric embedding in $\mathbb R^d$ is complete for the Existential Theory of the Reals for all $d\geq 3$ and $k\in\{d-1,d\}$. This implies that the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution. Moreover, this implies NP-hardness and constitutes the first hardness results for the algorithmic problem of geometric embedding (abstract simplicial) complexes.
Submission history
From: Linda Kleist [view email][v1] Thu, 5 Aug 2021 12:48:06 GMT (416kb,D)
[v2] Fri, 5 Nov 2021 11:12:44 GMT (671kb,D)
Link back to: arXiv, form interface, contact.