Geometric Embeddability of Complexes Is ∃R-Complete

Mikkel Abrahamsen; Linda Kleist; Tillmann Miltzow

doi:10.4230/LIPIcs.SoCG.2023.1

Geometric Embeddability of Complexes Is ∃R-Complete

Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in R^d 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
Subtitle of host publication	SoCG 2023, June 12-15, 2023, Dallas, Texas, USA
Editors	Erin W. Chambers, Joachim Gudmundsson
Publisher	Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
Pages	1:1-1:19
Number of pages	19
ISBN (Electronic)	9783959772730
ISBN (Print)	978-3-95977-273-0
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2023.1
Publication status	Published - 1 Jun 2023

Publication series

Name	Leibniz International Proceedings in Informatic
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume	258
ISSN (Print)	1868-8969

Bibliographical 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.

Keywords

simplicial complex
geometric embedding
linear embedding
hypergraph
recognition
existential theory of the reals

Access to Document

10.4230/LIPIcs.SoCG.2023.1Licence: CC BY

LIPIcs-SoCG-2023-1Final published version, 1.68 MBLicence: CC BY

Cite this

Abrahamsen, M., Kleist, L., & Miltzow, T. (2023). Geometric Embeddability of Complexes Is ∃R-Complete. In E. W. Chambers, & J. Gudmundsson (Eds.), 39th International Symposium on Computational Geometry, SoCG 2023: SoCG 2023, June 12-15, 2023, Dallas, Texas, USA (pp. 1:1-1:19). (Leibniz International Proceedings in Informatic; Vol. 258). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.SoCG.2023.1

Abrahamsen, Mikkel ; Kleist, Linda ; Miltzow, Tillmann. / Geometric Embeddability of Complexes Is ∃R-Complete. 39th International Symposium on Computational Geometry, SoCG 2023: SoCG 2023, June 12-15, 2023, Dallas, Texas, USA. editor / Erin W. Chambers ; Joachim Gudmundsson. Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, 2023. pp. 1:1-1:19 (Leibniz International Proceedings in Informatic).

@inproceedings{2f1642aa2ec64586bdfbd4d2074a3a8f,

title = "Geometric Embeddability of Complexes Is ∃R-Complete",

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}. 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.",

keywords = "simplicial complex, geometric embedding, linear embedding, hypergraph, recognition, existential theory of the reals",

author = "Mikkel Abrahamsen and Linda Kleist and Tillmann Miltzow",

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: {\textcopyright} Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow; licensed under Creative Commons License CC-BY 4.0.",

year = "2023",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2023.1",

language = "English",

isbn = "978-3-95977-273-0",

series = "Leibniz International Proceedings in Informatic",

publisher = "Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik GmbH",

pages = "1:1--1:19",

editor = "Chambers, {Erin W.} and Joachim Gudmundsson",

booktitle = "39th International Symposium on Computational Geometry, SoCG 2023",

}

Abrahamsen, M, Kleist, L & Miltzow, T 2023, Geometric Embeddability of Complexes Is ∃R-Complete. in EW Chambers & J Gudmundsson (eds), 39th International Symposium on Computational Geometry, SoCG 2023: SoCG 2023, June 12-15, 2023, Dallas, Texas, USA. Leibniz International Proceedings in Informatic, vol. 258, Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, pp. 1:1-1:19. https://doi.org/10.4230/LIPIcs.SoCG.2023.1

Geometric Embeddability of Complexes Is ∃R-Complete. / Abrahamsen, Mikkel; Kleist, Linda; Miltzow, Tillmann.
39th International Symposium on Computational Geometry, SoCG 2023: SoCG 2023, June 12-15, 2023, Dallas, Texas, USA. ed. / Erin W. Chambers; Joachim Gudmundsson. Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, 2023. p. 1:1-1:19 (Leibniz International Proceedings in Informatic; Vol. 258).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Geometric Embeddability of Complexes Is ∃R-Complete

AU - Abrahamsen, Mikkel

AU - Kleist, Linda

AU - Miltzow, Tillmann

N1 - 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.

PY - 2023/6/1

Y1 - 2023/6/1

N2 - 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.

AB - 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.

KW - simplicial complex

KW - geometric embedding

KW - linear embedding

KW - hypergraph

KW - recognition

KW - existential theory of the reals

UR - http://www.scopus.com/inward/record.url?scp=85163072339&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2023.1

DO - 10.4230/LIPIcs.SoCG.2023.1

M3 - Conference contribution

SN - 978-3-95977-273-0

T3 - Leibniz International Proceedings in Informatic

SP - 1:1-1:19

BT - 39th International Symposium on Computational Geometry, SoCG 2023

A2 - Chambers, Erin W.

A2 - Gudmundsson, Joachim

PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH

ER -

Abrahamsen M, Kleist L, Miltzow T. Geometric Embeddability of Complexes Is ∃R-Complete. In Chambers EW, Gudmundsson J, editors, 39th International Symposium on Computational Geometry, SoCG 2023: SoCG 2023, June 12-15, 2023, Dallas, Texas, USA. Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. 2023. p. 1:1-1:19. (Leibniz International Proceedings in Informatic). doi: 10.4230/LIPIcs.SoCG.2023.1

Geometric Embeddability of Complexes Is ∃R-Complete

Abstract

Publication series

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this