Embeddability in R 3 is NP-hard

DOI10.1145/3396593zbMath1491.68079OpenAlexW3033818404WikidataQ105336413 ScholiaQ105336413MaRDI QIDQ5133975

Arnaud de Mesmay, Martin Tancer, Yo'av Rieck, Eric Sedgwick

Publication date: 11 November 2020

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3396593

zbMATH Keywords

embeddingsimplicial complexDehn surgeryNP-hardness3-manifoldcomputational topology

Mathematics Subject Classification ID

Surgery and handlebodies (57R65) Embeddings in differential topology (57R40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of simplicial complexes (05E45)

Related Items

Graph theory -- a survey on the occasion of the Abel Prize for László Lovász ⋮ Embedding dimensions of simplicial complexes on few vertices