The computational complexity of knot and link problems
From MaRDI portal
Abstract: We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted, capable of being continuously deformed without self-intersection so that it lies in a plane. We show that this problem, {sc unknotting problem} is in {�f NP}. We also consider the problem, {sc unknotting problem} of determining whether two or more such polygons can be split, or continuously deformed without self-intersection so that they occupy both sides of a plane without intersecting it. We show that it also is in NP. Finally, we show that the problem of determining the genus of a polygonal knot (a generalization of the problem of determining whether it is unknotted) is in {�f PSPACE}. We also give exponential worst-case running time bounds for deterministic algorithms to solve each of these problems. These algorithms are based on the use of normal surfaces and decision procedures due to W. Haken, with recent extensions by W. Jaco and J. L. Tollefson.
Recommendations
Cited in
(76)- Fast algorithms for computing Jones polynomials of certain links
- Morphing polyhedra with parallel faces: Counterexamples
- Non-orientable fundamental surfaces in Lens spaces
- Converting between quadrilateral and standard solution sets in normal surface theory
- A new algorithm for recognizing the unknot
- The complexity of lattice knots
- Models of random knots
- Finding non-orientable surfaces in 3-manifolds
- The intersection of subgroups in free groups and linear programming
- Pole dancing: 3D morphs for tree drawings
- Identifying lens spaces in polynomial time
- The parametrized complexity of knot polynomials
- The disjoint curve property
- The efficient certification of knottedness and Thurston norm
- On the hardness of finding normal surfaces
- Traversing three-manifold triangulations and spines
- Cuts for 3-D magnetic scalar potentials: visualizing unintuitive surfaces arising from trivial knots
- Some conditionally hard problems on links and 3-manifolds
- Maximal admissible faces and asymptotic bounds for the normal surface solution space
- Knottedness is in NP, modulo GRH
- The computational complexity of basic decision problems in 3-dimensional topology
- The unbearable hardness of unknotting
- The number of Reidemeister moves needed for unknotting
- Efficient knot discrimination via quandle coloring with SAT and \#-SAT
- Post quantum cryptography from mutant prime knots
- Unknotting is in \(\mathsf{AM} \cap \mathsf{co-AM}\)
- An efficient algorithm to decide the knot problem
- On the complexity of torus knot recognition
- On Jones' subgroup of R. Thompson group F
- On the unknotting problem
- Optimizing the double description method for normal surface enumeration
- Automata on Gauss Words
- scientific article; zbMATH DE number 1303213 (Why is no real title available?)
- scientific article; zbMATH DE number 1305557 (Why is no real title available?)
- TOWARDS AN IMPLEMENTATION OF THE B–H ALGORITHM FOR RECOGNIZING THE UNKNOT
- Normal and Jones surfaces of knots
- Computing Heegaard genus is NP-hard
- Recognition algorithms in knot theory
- A polynomial upper bound on Reidemeister moves
- Alternating links have at most polynomially many Seifert surfaces of fixed genus
- NP-hard problems naturally arising in knot theory
- Rectangular knot diagrams classification with deep learning
- Smoothing the Gap Between NP and ER
- The unbearable hardness of unknotting
- Link crossing number is NP-hard
- New presentations of a link and virtual link
- Pole dancing: 3D morphs for tree drawings
- Design tools for reporter strands and DNA origami scaffold strands
- Computing invariants of knotted graphs given by sequences of points in 3-dimensional space
- The least spanning area of a knot and the optimal bounding chain problem
- The computational complexity of knot genus and spanning area
- Detecting Unknots via Equational Reasoning, I: Exploration
- A classification of slow convergence near parametric periodic points of discrete dynamical systems
- Low complexity algorithms in knot theory
- Tracing compressed curves in triangulated surfaces
- The computational complexity of knot genus in a fixed 3‐manifold
- Computing a link diagram from its exterior
- Algorithms for contractibility of compressed curves on 3-manifold boundaries
- The computational complexity of classical knot recognition
- Hardness of embedding simplicial complexes in R^d
- Yarn ball knots and faster computations
- Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
- The computational complexity of the solid torus core recognition problem
- Recognition of Seifert fibered spaces with boundary is in NP
- Linear bounds of the crosscap number of knots
- Hopf arborescent links, minor theory, and decidability of the genus defect
- Localized geometric moves to compute hyperbolic structures on triangulated 3-manifolds
- A new and efficient meshfree method to solve partial differential equations: application to three-dimensional transient heat transfer problems
- Complexity of 3-manifolds obtained by Dehn filling
- Algorithms for contractibility of compressed curves on 3-manifold boundaries
- Hopf arborescent links, minor theory, and decidability of the genus defect
- A structural approach to tree decompositions of knots and spatial graphs
- A practical algorithm for knot factorisation
- Hard diagrams of split links
- Preserving computational topology by subdivision of quadratic and cubic Bézier curves
- Crosscap numbers and the Jones polynomial
This page was built for publication: The computational complexity of knot and link problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3158535)
