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
(71)- scientific article; zbMATH DE number 1305557 (Why is no real title available?)
- The computational complexity of basic decision problems in 3-dimensional topology
- New presentations of a link and virtual link
- The parametrized complexity of knot polynomials
- Pole dancing: 3D morphs for tree drawings
- Automata on Gauss Words
- Complexity of 3-manifolds obtained by Dehn filling
- Knottedness is in NP, modulo GRH
- Post quantum cryptography from mutant prime knots
- Localized geometric moves to compute hyperbolic structures on triangulated 3-manifolds
- Traversing three-manifold triangulations and spines
- Computing a link diagram from its exterior
- Hardness of embedding simplicial complexes in R^d
- Optimizing the double description method for normal surface enumeration
- Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
- A classification of slow convergence near parametric periodic points of discrete dynamical systems
- An efficient algorithm to decide the knot problem
- Tracing compressed curves in triangulated surfaces
- Algorithms for contractibility of compressed curves on 3-manifold boundaries
- Identifying lens spaces in polynomial time
- The complexity of lattice knots
- A new and efficient meshfree method to solve partial differential equations: application to three-dimensional transient heat transfer problems
- Link crossing number is NP-hard
- A new algorithm for recognizing the unknot
- Rectangular knot diagrams classification with deep learning
- Preserving computational topology by subdivision of quadratic and cubic Bézier curves
- Efficient knot discrimination via quandle coloring with SAT and \#-SAT
- Computing Heegaard genus is NP-hard
- On the unknotting problem
- The number of Reidemeister moves needed for unknotting
- NP-hard problems naturally arising in knot theory
- On the complexity of torus knot recognition
- Pole dancing: 3D morphs for tree drawings
- Algorithms for contractibility of compressed curves on 3-manifold boundaries
- Detecting Unknots via Equational Reasoning, I: Exploration
- The unbearable hardness of unknotting
- The disjoint curve property
- Fast algorithms for computing Jones polynomials of certain links
- The computational complexity of knot genus and spanning area
- Morphing polyhedra with parallel faces: Counterexamples
- Non-orientable fundamental surfaces in Lens spaces
- On Jones' subgroup of R. Thompson group F
- Crosscap numbers and the Jones polynomial
- Converting between quadrilateral and standard solution sets in normal surface theory
- Normal and Jones surfaces of knots
- The computational complexity of knot genus in a fixed 3‐manifold
- The intersection of subgroups in free groups and linear programming
- scientific article; zbMATH DE number 7559249 (Why is no real title available?)
- Linear bounds of the crosscap number of knots
- The least spanning area of a knot and the optimal bounding chain problem
- On the hardness of finding normal surfaces
- Models of random knots
- Alternating links have at most polynomially many Seifert surfaces of fixed genus
- The computational complexity of the solid torus core recognition problem
- Finding non-orientable surfaces in 3-manifolds
- Low complexity algorithms in knot theory
- Hopf arborescent links, minor theory, and decidability of the genus defect
- A polynomial upper bound on Reidemeister moves
- Computing invariants of knotted graphs given by sequences of points in 3-dimensional space
- Recognition of Seifert fibered spaces with boundary is in NP
- The efficient certification of knottedness and Thurston norm
- The computational complexity of classical knot recognition
- Maximal admissible faces and asymptotic bounds for the normal surface solution space
- TOWARDS AN IMPLEMENTATION OF THE B–H ALGORITHM FOR RECOGNIZING THE UNKNOT
- Smoothing the Gap Between NP and ER
- Unknotting is in \(\mathsf{AM} \cap \mathsf{co-AM}\)
- Some conditionally hard problems on links and 3-manifolds
- Cuts for 3-D magnetic scalar potentials: visualizing unintuitive surfaces arising from trivial knots
- Recognition algorithms in knot theory
- Yarn ball knots and faster computations
- Design tools for reporter strands and DNA origami scaffold strands
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)
