Can I read Geometric Embeddability of Complexes is $\exists \mathbb R$-complete on EtoBox?

Geometric Embeddability of Complexes is $\exists \mathbb R$-complete by Abrahamsen, Mikkel; Kleist, Linda; Miltzow, Tillmann is a scholarly article available to read on EtoBox.

What is Geometric Embeddability of Complexes is $\exists \mathbb R$-complete about?

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.

Author

Abrahamsen, Mikkel; Kleist, Linda; Miltzow, Tillmann

Published

2021

Language

EN