Geometric Embeddability of Complexes Is ∃R-Complete
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 1,68 MB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | 39th International Symposium on Computational Geometry, SoCG 2023 |
Redaktører | Erin W. Chambers, Joachim Gudmundsson |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2023 |
Artikelnummer | 1 |
ISBN (Elektronisk) | 9783959772730 |
DOI | |
Status | Udgivet - 2023 |
Begivenhed | 39th International Symposium on Computational Geometry, SoCG 2023 - Dallas, USA Varighed: 12 jun. 2023 → 15 jun. 2023 |
Konference
Konference | 39th International Symposium on Computational Geometry, SoCG 2023 |
---|---|
Land | USA |
By | Dallas |
Periode | 12/06/2023 → 15/06/2023 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 258 |
ISSN | 1868-8969 |
Bibliografisk note
Funding Information:
Funding Mikkel Abrahamsen: Supported by Starting Grant 1054-00032B from the Independent Research Fund Denmark under the Sapere Aude research career programme and part of Basic Algorithms Research Copenhagen (BARC), supported by the VILLUM Foundation grant 16582. Linda Kleist: Partially supported by a postdoc fellowship of the German Academic Exchange Service (DAAD). Tillmann Miltzow: Generously supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 016.Veni.192.250.
Publisher Copyright:
© Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow; licensed under Creative Commons License CC-BY 4.0.
ID: 384029530