Some conditionally hard problems on links and 3-manifolds
From MaRDI portal
Publication:2411821
DOI10.1007/s00454-017-9905-8zbMath1384.57010arXiv1602.08427OpenAlexW2964069834MaRDI QIDQ2411821
Publication date: 25 October 2017
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1602.08427
Related Items
The unbearable hardness of unknotting, Finding non-orientable surfaces in 3-manifolds, Algorithms for contractibility of compressed curves on 3-manifold boundaries, Computing Heegaard Genus is NP-Hard, Link crossing number is NP-hard, Coloring invariants of knots and links are often intractable, Unnamed Item, Unnamed Item, NP–hard problems naturally arising in knot theory
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of immersed normal surfaces
- The homeomorphism problem for closed 3-manifolds
- Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
- An algorithm to decide if a 3-manifold is a Haken manifold
- On the classification of homeomorphisms of 2-manifolds and the classification of 3-manifolds
- Canonical decompositions of 3-manifolds
- Knots.
- Geometrisation of 3-manifolds
- The efficient certification of knottedness and Thurston norm
- Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization
- Knottedness is in NP, modulo GRH
- The number of Reidemeister moves needed for unknotting
- The computational complexity of knot and link problems
- 3-manifold knot genus is NP-complete
- Elementary knot theory
- Graph isomorphism in quasipolynomial time [extended abstract]
- The computational complexity of knot genus and spanning area
- The complexity of detecting taut angle structures on triangulations
- Algorithmic topology and classification of 3-manifolds
- Computational Complexity
