Geometric Embeddability of Complexes Is ∃R-Complete
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Fulltext
Final published version, 1.68 MB, PDF document
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}. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution and other important problems from various fields related to packing, Nash equilibria, minimum convex covers, the Art Gallery Problem, continuous constraint satisfaction problems, and training neural networks. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometric embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability.
Original language | English |
---|---|
Title of host publication | 39th International Symposium on Computational Geometry, SoCG 2023 |
Editors | Erin W. Chambers, Joachim Gudmundsson |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2023 |
Article number | 1 |
ISBN (Electronic) | 9783959772730 |
DOIs | |
Publication status | Published - 2023 |
Event | 39th International Symposium on Computational Geometry, SoCG 2023 - Dallas, United States Duration: 12 Jun 2023 → 15 Jun 2023 |
Conference
Conference | 39th International Symposium on Computational Geometry, SoCG 2023 |
---|---|
Land | United States |
By | Dallas |
Periode | 12/06/2023 → 15/06/2023 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 258 |
ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:
© Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow; licensed under Creative Commons License CC-BY 4.0.
- existential theory of the reals, geometric embedding, hypergraph, linear embedding, recognition, simplicial complex
Research areas
ID: 384029530