The computational complexity of classical knot recognition

DOI10.1142/S0218216523500694MaRDI QIDQ6181209zbMATH OpenOpenAlexFDO

Authors Kazuhiro Ichihara, Seiichi Tani

Publication date 2 January 2024

Published in Journal of Knot Theory and Its Ramifications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.02988

zbMATH Keywords

algorithmscomputational complexityvirtual knots

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Generalized knots (virtual knots, welded knots, quandles, etc.) (57K12)

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.

Recommendations

• On the complexity of torus knot recognition
• The computational complexity of knot and link problems
• NP-hard problems naturally arising in knot theory
• The computational complexity of knot genus and spanning area
• Knottedness is in NP, modulo GRH

Cites work

• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• 0-efficient triangulations of 3-manifolds
• A new approach to crushing 3-manifold triangulations
• ABSTRACT LINK DIAGRAMS AND VIRTUAL KNOTS
• Algorithmic topology and classification of 3-manifolds
• Algorithms for the complete decomposition of a closed 3-manifold
• An algorithm to decide if a 3-manifold is a Haken manifold
• Computational topology with Regina: algorithms, heuristics and implementations
• Converting between quadrilateral and standard solution sets in normal surface theory
• Introducing Regina, The 3-Manifold Topology Software
• Optimizing the double description method for normal surface enumeration
• STABLE EQUIVALENCE OF KNOTS ON SURFACES AND VIRTUAL KNOT COBORDISMS
• The complexity of the normal surface solution space
• The computational complexity of knot and link problems
• The efficient certification of knottedness and Thurston norm
• Virtual knot theory
• Virtual knots and links
• What is a virtual link?

Cited in

(2)

• Knottedness is in NP, modulo GRH
• Recognition algorithms in knot theory

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)