Session S28 - Knots, Surfaces, 3-manifolds

Thursday, July 15, 19:20 ~ 19:50 UTC-3

Embeddability in $\mathbb R^3$ is NP-hard

Eric Sedgwick

DePaul University, United States   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

We prove that the problem of deciding whether a 2–or 3–dimensional simplicial complex embeds into $\mathbb R^3$ is NP-hard. This stands in contrast with the lower dimensional cases which can be solved in linear time, and a variety of computational problems in $\mathbb R^3$ like unknot or 3–sphere recognition which are in NP ∩ co-NP (assuming the generalized Riemann hypothesis). Our reduction encodes a satisfiability instance into the embeddability problem of a 3–manifold with boundary tori, and relies extensively on techniques from low-dimensional topology, most importantly Dehn fillings on link complements.

Joint work with Arnaud de Mesmay (CNRS, GIPSA-Lab, France), Yo'av Rieck (University of Arkansas, USA) and Martin Tancer (Charles University, Czech Republic)..

View abstract PDF