The computational complexity of knot genus and spanning area

DOI10.1090/S0002-9947-05-03919-XzbMath1098.57003arXivmath/0205057MaRDI QIDQ5469952

Joel Hass, William P. Thurston, Ian Agol

Publication date: 29 May 2006

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0205057

zbMATH Keywords

complexityknotNP-hardgenusNP-complete3-manifoldcomputational topologynormal surface.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) General geometric structures on low-dimensional manifolds (57M50)

Related Items

Counting essential surfaces in \(3\)-manifolds, The complexity of identifying Ryu-Takayanagi surfaces in \(\mathrm{AdS}_{3 }\mathrm{CFT}_{2}\), Counting intersections of normal curves, A random tunnel number one 3-manifold does not fiber over the circle, Models of random knots, The unbearable hardness of unknotting, Some conditionally hard problems on links and 3-manifolds, On dual unit balls of Thurston norms, Crosscap numbers and the Jones polynomial, Experimental Statistics for Mirzakhani’s Theorem, Finding non-orientable surfaces in 3-manifolds, The computational complexity of knot genus in a fixed 3‐manifold, Traversing three-manifold triangulations and spines, Hardness of embedding simplicial complexes in \(\mathbb R^d\), The number of closed essential surfaces in Montesinos knots with four rational tangles, Algorithms for contractibility of compressed curves on 3-manifold boundaries, Cuts for 3-D magnetic scalar potentials: visualizing unintuitive surfaces arising from trivial knots, Coloring invariants of knots and links are often intractable, Detecting geometric splittings in finitely presented groups, The computational complexity of basic decision problems in 3-dimensional topology, Low complexity algorithms in knot theory, Unnamed Item, The efficient certification of knottedness and Thurston norm, Simplifying triangulations, Interval identification systems and plane sections of 3-periodic surfaces, Tracing compressed curves in triangulated surfaces, Parameterized Complexity of Discrete Morse Theory, NP–hard problems naturally arising in knot theory, On the complexity of torus knot recognition, Quadratic equations in hyperbolic groups are NP-complete

Cites Work

• Recursive unsolvability of group theoretic problems
• An algorithm to decide if a 3-manifold is a Haken manifold
• Ein Verfahren zur Aufspaltung einer 3-Mannigfaltigkeit in irreduzible 3- Mannigfaltigkeiten
• Algorithms for recognizing knots and 3-manifolds
• PL equivariant surgery and invariant decompositions of 3-manifolds
• Über das Geschlecht von Knoten
• Thin position and the recognition problem for \(S^ 3\)
• Algorithms for the complete decomposition of a closed \(3\)-manifold
• Affine structures in 3-manifolds. V: The triangulation theorem and Hauptvermutung
• The number of Reidemeister moves needed for unknotting
• The computational complexity of knot and link problems
• On the computational complexity of the Jones and Tutte polynomials
• The complexity of satisfiability problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item