Topology Seminar 

Title: Embeddability in R 3 is NP-hard 

Speaker: Eric Sedgwick, Depaul University 

Date: Oct 4, 2022 

Time: 2:30 PM 

Room: MSCS 101 

Abstract: We prove that the problem of deciding whether a 2–or 3–dimensional simplicial complex embeds into 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 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 lowdimensional 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).