Geometric Embeddability of Complexes is ∃ℝ-complete

Mikkel Abrahamsen; Linda Kleist; Tillmann Miltzow

doi:10.1145/3707201

Geometric Embeddability of Complexes is ∃ℝ-complete

Mikkel Abrahamsen
, Linda Kleist^*
, Tillmann Miltzow

^*Corresponding author for this work

Sub Algorithms and Complexity

University of Copenhagen
University of Potsdam

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in ℝ^d is complete for the Existential Theory of the Reals for all d ≥ 3 and k ϵ {d-1, d} by reducing from pseudoline stretchability. Consequently, 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 result for the algorithmic problem of geometrically embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability [Matoušek, Sedgwick, Tancer, and Wagner, J. ACM 2018, and de Mesmay, Rieck, Sedgwick and Tancer, J. ACM 2020] and establishes connections to computational topology.

Original language	English
Article number	9
Number of pages	26
Journal	Journal of the ACM
Volume	72
Issue number	1
DOIs	https://doi.org/10.1145/3707201
Publication status	Published - 24 Jan 2025

Bibliographical note

Publisher Copyright:
© 2025 Copyright held by the owner/author(s).

Funding

Tillmann Miltzow supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 016.Veni.192.250. Linda Kleist supported by a postdoc fellowship of the German Academic Exchange Service (DAAD). 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.

Funders	Funder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek
Deutscher Akademischer Austauschdienst
Basic Algorithms Research Copenhagen, University of Copenhagen
Independent Research Fund Denmark
VILLUM FONDEN	16582

Keywords

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

Access to Document

10.1145/3707201Licence: CC BY-NC-SA

Geometric Embeddability of Complexes is ∃ℝ-completeFinal published version, 1.52 MBLicence: CC BY-NC-SA

Cite this

@article{5a0bfaba98964e4bb1eb1091fff696d6,

title = "Geometric Embeddability of Complexes is ∃ℝ-complete",

abstract = "We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in ℝd is complete for the Existential Theory of the Reals for all d ≥ 3 and k ϵ \{d-1, d\} by reducing from pseudoline stretchability. Consequently, 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 result for the algorithmic problem of geometrically embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability [Matou{\v s}ek, Sedgwick, Tancer, and Wagner, J. ACM 2018, and de Mesmay, Rieck, Sedgwick and Tancer, J. ACM 2020] and establishes connections to computational topology.",

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

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

note = "Publisher Copyright: {\textcopyright} 2025 Copyright held by the owner/author(s).",

year = "2025",

month = jan,

day = "24",

doi = "10.1145/3707201",

language = "English",

volume = "72",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery",

number = "1",

}

TY - JOUR

T1 - Geometric Embeddability of Complexes is ∃ℝ-complete

AU - Abrahamsen, Mikkel

AU - Kleist, Linda

AU - Miltzow, Tillmann

PY - 2025/1/24

Y1 - 2025/1/24

N2 - We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in ℝd is complete for the Existential Theory of the Reals for all d ≥ 3 and k ϵ {d-1, d} by reducing from pseudoline stretchability. Consequently, 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 result for the algorithmic problem of geometrically embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability [Matoušek, Sedgwick, Tancer, and Wagner, J. ACM 2018, and de Mesmay, Rieck, Sedgwick and Tancer, J. ACM 2020] and establishes connections to computational topology.

AB - We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in ℝd is complete for the Existential Theory of the Reals for all d ≥ 3 and k ϵ {d-1, d} by reducing from pseudoline stretchability. Consequently, 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 result for the algorithmic problem of geometrically embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability [Matoušek, Sedgwick, Tancer, and Wagner, J. ACM 2018, and de Mesmay, Rieck, Sedgwick and Tancer, J. ACM 2020] and establishes connections to computational topology.

KW - existential theory of the reals

KW - geometric embedding

KW - hypergraph

KW - linear embedding

KW - recognition

KW - Simplicial complex

UR - https://www.scopus.com/pages/publications/85217145767

U2 - 10.1145/3707201

DO - 10.1145/3707201

M3 - Article

AN - SCOPUS:85217145767

SN - 0004-5411

VL - 72

JO - Journal of the ACM

JF - Journal of the ACM

IS - 1

M1 - 9

ER -

Geometric Embeddability of Complexes is ∃ℝ-complete

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this