Geometric Embeddability of Complexes Is ∃R-Complete

Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.

Original languageEnglish
Title of host publication39th International Symposium on Computational Geometry, SoCG 2023
Subtitle of host publicationSoCG 2023, June 12-15, 2023, Dallas, Texas, USA
EditorsErin W. Chambers, Joachim Gudmundsson
PublisherSchloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
Pages1:1-1:19
Number of pages19
ISBN (Electronic)9783959772730
ISBN (Print)978-3-95977-273-0
DOIs
Publication statusPublished - 1 Jun 2023

Publication series

NameLeibniz International Proceedings in Informatic
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume258
ISSN (Print)1868-8969

Keywords

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

Fingerprint

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

Cite this