NP–hard problems naturally arising in knot theory

DOI10.1090/btran/71zbMath1468.57005arXiv1809.10334OpenAlexW3172343102MaRDI QIDQ4997304

Anastasiia Tsvietkova, Dale Koenig

Publication date: 29 June 2021

Published in: Transactions of the American Mathematical Society, Series B (Search for Journal in Brave)

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

zbMATH Keywords

diagramknotsplitting numberNP-hardNP-completeunlinking numberReidemeister movesublink

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Knot theory (57K10) Computational methods for problems pertaining to manifolds and cell complexes (57-08)

Cites Work

• Unnamed Item
• Unnamed Item
• A polynomial upper bound on Reidemeister moves
• Closed incompressible surfaces in alternating knot and link complements
• Unknotting genus one knots
• The number of Reidemeister moves for splitting a link
• Some conditionally hard problems on links and 3-manifolds
• The unbearable hardness of unknotting
• The number of Reidemeister moves needed for unknotting
• An upper bound on Reidemeister moves
• P, NP, and NP-Completeness
• The computational complexity of knot and link problems
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Elementary knot theory
• The computational complexity of knot genus and spanning area