The computational complexity of knot and link problems
From MaRDI portal
Publication:3158535
DOI10.1145/301970.301971zbMath1065.68667arXivmath/9807016OpenAlexW2068497209WikidataQ29011807 ScholiaQ29011807MaRDI QIDQ3158535
Joel Hass, Jeffrey C. Lagarias, Nicholas J. Pippenger
Publication date: 25 January 2005
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/9807016
Related Items
The parametrized complexity of knot polynomials, The disjoint curve property, POST QUANTUM CRYPTOGRAPHY FROM MUTANT PRIME KNOTS, Rectangular knot diagrams classification with deep learning, TOWARDS AN IMPLEMENTATION OF THE B–H ALGORITHM FOR RECOGNIZING THE UNKNOT, On Jones' subgroup of R. Thompson group \(F\), Smoothing the Gap Between NP and ER, Models of random knots, Normal and Jones surfaces of knots, The unbearable hardness of unknotting, Some conditionally hard problems on links and 3-manifolds, Preserving computational topology by subdivision of quadratic and cubic Bézier curves, Crosscap numbers and the Jones polynomial, Finding non-orientable surfaces in 3-manifolds, Traversing three-manifold triangulations and spines, Hardness of embedding simplicial complexes in \(\mathbb R^d\), Computing a link diagram from its exterior, Algorithms for contractibility of compressed curves on 3-manifold boundaries, The computational complexity of classical knot recognition, Maximal admissible faces and asymptotic bounds for the normal surface solution space, Computing Heegaard Genus is NP-Hard, Cuts for 3-D magnetic scalar potentials: visualizing unintuitive surfaces arising from trivial knots, Link crossing number is NP-hard, A tree traversal algorithm for decision problems in knot theory and 3-manifold topology, The intersection of subgroups in free groups and linear programming, The number of Reidemeister moves needed for unknotting, Knottedness is in NP, modulo GRH, Pole dancing: 3D morphs for tree drawings, A polynomial upper bound on Reidemeister moves, Identifying lens spaces in polynomial time, Design tools for reporter strands and DNA origami scaffold strands, The computational complexity of basic decision problems in 3-dimensional topology, A classification of slow convergence near parametric periodic points of discrete dynamical systems, Optimizing the double description method for normal surface enumeration, Low complexity algorithms in knot theory, Unnamed Item, The efficient certification of knottedness and Thurston norm, Automata on Gauss Words, The computational complexity of knot genus and spanning area, Tracing compressed curves in triangulated surfaces, Efficient Knot Discrimination via Quandle Coloring with SAT and #-SAT, New presentations of a link and virtual link, Fast algorithms for computing Jones polynomials of certain links, Morphing polyhedra with parallel faces: Counterexamples, On the hardness of finding normal surfaces, Non-orientable fundamental surfaces in Lens spaces, A new algorithm for recognizing the unknot, Pole Dancing: 3D Morphs for Tree Drawings, Converting between quadrilateral and standard solution sets in normal surface theory, Detecting Unknots via Equational Reasoning, I: Exploration, Alternating links have at most polynomially many Seifert surfaces of fixed genus, NP–hard problems naturally arising in knot theory, On the complexity of torus knot recognition
