NP–hard problems naturally arising in knot theory

DOI10.1090/btran/71zbMath1468.57005arXiv1809.10334MaRDI 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

diagram; knot; splitting number; NP-hard; NP-complete; unlinking number; Reidemeister move; sublink

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

57K10: Knot theory

57-08: Computational methods for problems pertaining to manifolds and cell complexes