Abstract: 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$\cap$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. This is joint work with Arnaud de Mesmay (CNRS, GIPSA-Lab, France), Yo'av Rieck (University of Arkansas, USA) and Martin Tancer (Charles University, Czech Republic).
To add/edit talks, please log in on the department web page, then return to Announce. Alternatively if you know the Announce
username/password, click the link below: