The computational complexity of classical knot recognition
From MaRDI portal
Publication:6181209
DOI10.1142/S0218216523500694arXiv2206.02988OpenAlexW4386707872MaRDI QIDQ6181209FDOQ6181209
Authors: Kazuhiro Ichihara, Seiichi Tani 
Publication date: 2 January 2024
Published in: Journal of Knot Theory and Its Ramifications (Search for Journal in Brave)
Abstract: The classical knot recognition problem is the problem of determining whether the virtual knot represented by a given diagram is classical. We prove that this problem is in NP, and we give an exponential time algorithm for the problem.
Full work available at URL: https://arxiv.org/abs/2206.02988
Recommendations
Analysis of algorithms and problem complexity (68Q25) Generalized knots (virtual knots, welded knots, quandles, etc.) (57K12)
Cites Work
- Title not available (Why is that?)
- Algorithms for the complete decomposition of a closed \(3\)-manifold
- Virtual knot theory
- What is a virtual link?
- ABSTRACT LINK DIAGRAMS AND VIRTUAL KNOTS
- 0-efficient triangulations of 3-manifolds
- Computational topology with Regina: algorithms, heuristics and implementations
- Introducing Regina, The 3-Manifold Topology Software
- Algorithmic topology and classification of 3-manifolds
- An algorithm to decide if a 3-manifold is a Haken manifold
- The computational complexity of knot and link problems
- STABLE EQUIVALENCE OF KNOTS ON SURFACES AND VIRTUAL KNOT COBORDISMS
- Virtual knots and links
- A new approach to crushing 3-manifold triangulations
- Converting between quadrilateral and standard solution sets in normal surface theory
- Optimizing the double description method for normal surface enumeration
- The efficient certification of knottedness and Thurston norm
- The complexity of the normal surface solution space
Cited In (2)
This page was built for publication: The computational complexity of classical knot recognition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6181209)
