Geometric Embeddability of Complexes is $\exists \mathbb{R}$-complete

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\ge 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.

arXiv comment26 pages, 18 figures

References in corpus (7)

• Recognition and Complexity of Point Visibility Graphs
• Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension
• A universality theorem for nonnegative matrix factorizations
• Embedding simply connected 2-complexes in 3-space -- V. A refined Kuratowski-type characterisation
• A Universality Theorem for Nested Polytopes
• On the Complexity of Embeddable Simplicial Complexes
• On embeddability of joins and their `factors'