Embeddability in R 3 is NP-hard

DOI10.1145/3396593zbMath1491.68079WikidataQ105336413 ScholiaQ105336413MaRDI QIDQ5133975

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

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

embedding; simplicial complex; Dehn surgery; NP-hardness; 3-manifold; computational topology

Mathematics Subject Classification ID

57R65: Surgery and handlebodies

57R40: Embeddings in differential topology

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05E45: Combinatorial aspects of simplicial complexes