Geometric Embeddability of Complexes is ∃R-complete

Mikkel Abrahamsen, Linda Kleist, Till Miltzow

Research output: Working paperPreprintAcademic

Abstract

We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in Rd is complete for the Existential Theory of the Reals for all d≥3 and k∈{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.
Original languageEnglish
PublisherarXiv
Pages1-27
DOIs
Publication statusPublished - 5 Nov 2021

Fingerprint

Dive into the research topics of 'Geometric Embeddability of Complexes is ∃R-complete'. Together they form a unique fingerprint.

Cite this