## View abstract

### 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. document.getElementById('cloak1e137aa77e007383c5a55dfe5bac75cd').innerHTML = ''; var prefix = '&#109;a' + 'i&#108;' + '&#116;o'; var path = 'hr' + 'ef' + '='; var addy1e137aa77e007383c5a55dfe5bac75cd = '&#101;s&#101;dgw&#105;ck' + '&#64;'; addy1e137aa77e007383c5a55dfe5bac75cd = addy1e137aa77e007383c5a55dfe5bac75cd + 'cdm' + '&#46;' + 'd&#101;p&#97;&#117;l' + '&#46;' + '&#101;d&#117;'; var addy_text1e137aa77e007383c5a55dfe5bac75cd = '&#101;s&#101;dgw&#105;ck' + '&#64;' + 'cdm' + '&#46;' + 'd&#101;p&#97;&#117;l' + '&#46;' + '&#101;d&#117;';document.getElementById('cloak1e137aa77e007383c5a55dfe5bac75cd').innerHTML += '<a ' + path + '\'' + prefix + ':' + addy1e137aa77e007383c5a55dfe5bac75cd + '\'>'+addy_text1e137aa77e007383c5a55dfe5bac75cd+'<\/a>';

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)..