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 (53)
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
This page was built for publication: The computational complexity of knot and link problems
