Geometric Embeddability of Complexes is ∃R-complete

Mikkel Abrahamsen; Linda Kleist; Till Miltzow

doi:10.48550/arXiv.2108.02585

Geometric Embeddability of Complexes is ∃R-complete

Mikkel Abrahamsen
, Linda Kleist
, Till Miltzow

Research output: Working paper › Preprint › Academic

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}. This implies that 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 results for the algorithmic problem of geometric embedding (abstract simplicial) complexes.

Original language	English
Publisher	arXiv
Pages	1-27
DOIs	https://doi.org/10.48550/arXiv.2108.02585
Publication status	Published - 5 Nov 2021

Access to Document

10.48550/arXiv.2108.02585

2108.02585Submitted manuscript, 1.73 MB

Cite this

@techreport{73e766bfb82b4e7aa5b14cddebfec7c3,

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\}. This implies that 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 results for the algorithmic problem of geometric embedding (abstract simplicial) complexes.",

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

year = "2021",

month = nov,

day = "5",

doi = "10.48550/arXiv.2108.02585",

language = "English",

pages = "1--27",

publisher = "arXiv",

type = "WorkingPaper",

institution = "arXiv",

}

TY - UNPB

T1 - Geometric Embeddability of Complexes is ∃R-complete

AU - Abrahamsen, Mikkel

AU - Kleist, Linda

AU - Miltzow, Till

PY - 2021/11/5

Y1 - 2021/11/5

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}. This implies that 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 results for the algorithmic problem of geometric embedding (abstract simplicial) complexes.

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}. This implies that 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 results for the algorithmic problem of geometric embedding (abstract simplicial) complexes.

U2 - 10.48550/arXiv.2108.02585

DO - 10.48550/arXiv.2108.02585

M3 - Preprint

SP - 1

EP - 27

BT - Geometric Embeddability of Complexes is ∃R-complete

PB - arXiv

ER -

Geometric Embeddability of Complexes is ∃R-complete

Abstract

Access to Document

Fingerprint

Cite this