Some Conditionally Hard Problems on Links and 3-Manifolds
Lists
Only you see this
Abstract
We show that three natural decision problems about links and 3-manifolds are computationally hard, assuming some conjectures in complexity theory. The first problem is determining whether a link in the 3-sphere bounds a Seifert surface with Thurston norm at most a given integer; this is shown to be NP-complete. The second problem is the homeomorphism problem for closed 3-manifolds; this is shown to be at least as hard as the graph isomorphism problem. The third problem is determining whether a given link in the 3-sphere is a sublink of another given link; this is shown to be NP-hard.
BibTeX
@article{lackenby2017some,
author = {Marc Lackenby},
title = {{Some Conditionally Hard Problems on Links and 3-Manifolds}},
journal = {Discret. Comput. Geom.},
year = {2017},
doi = {10.1007/s00454-017-9905-8},
}Loading related content...