NP–HARD PROBLEMS NATURALLY ARISING IN KNOT THEORY

Dale Koenig; Anastasiia Tsvietkova

doi:10.1090/btran/71

NP–HARD PROBLEMS NATURALLY ARISING IN KNOT THEORY

Dale Koenig, Anastasiia Tsvietkova

Rutgers Newark, Math & Computer Science

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

We prove that certain problems naturally arising in knot theory are NP–hard or NP–complete. These are the problems of obtaining one dia-gram from another one of a link in a bounded number of Reidemeister moves, determining whether a link has an unlinking or splitting number k, finding a k-component unlink as a sublink, and finding a k-component alternating sublink.

Original language	English (US)
Pages (from-to)	420-441
Number of pages	22
Journal	Transactions of the American Mathematical Society Series B
Volume	8
Issue number	15
DOIs	https://doi.org/10.1090/btran/71
State	Published - May 27 2021

All Science Journal Classification (ASJC) codes

Mathematics (miscellaneous)

Access to Document

10.1090/btran/71

Cite this

@article{076b939bc9ef4e3aa0c703035abb3d43,

title = "NP–HARD PROBLEMS NATURALLY ARISING IN KNOT THEORY",

abstract = "We prove that certain problems naturally arising in knot theory are NP–hard or NP–complete. These are the problems of obtaining one dia-gram from another one of a link in a bounded number of Reidemeister moves, determining whether a link has an unlinking or splitting number k, finding a k-component unlink as a sublink, and finding a k-component alternating sublink.",

author = "Dale Koenig and Anastasiia Tsvietkova",

note = "Funding Information: Received by the editors March 19, 2020, and, in revised form, December 3, 2020. 2020 Mathematics Subject Classification. Primary 57K10, 57-08. The first author acknowledges support from NSF DMS-1664425 (previously 1406588) and NSF DMS-2005496 grants, and Insitute of Advanced Study (under DMS-1926686 grant). Both authors were supported by Okinawa Institute of Science and Technology funding. Publisher Copyright: {\textcopyright} 2021 by the authors.",

year = "2021",

month = may,

day = "27",

doi = "10.1090/btran/71",

language = "English (US)",

volume = "8",

pages = "420--441",

journal = "Transactions of the American Mathematical Society Series B",

issn = "2330-0000",

publisher = "American Mathematical Society",

number = "15",

}

TY - JOUR

T1 - NP–HARD PROBLEMS NATURALLY ARISING IN KNOT THEORY

AU - Koenig, Dale

AU - Tsvietkova, Anastasiia

N1 - Funding Information: Received by the editors March 19, 2020, and, in revised form, December 3, 2020. 2020 Mathematics Subject Classification. Primary 57K10, 57-08. The first author acknowledges support from NSF DMS-1664425 (previously 1406588) and NSF DMS-2005496 grants, and Insitute of Advanced Study (under DMS-1926686 grant). Both authors were supported by Okinawa Institute of Science and Technology funding. Publisher Copyright: © 2021 by the authors.

PY - 2021/5/27

Y1 - 2021/5/27

N2 - We prove that certain problems naturally arising in knot theory are NP–hard or NP–complete. These are the problems of obtaining one dia-gram from another one of a link in a bounded number of Reidemeister moves, determining whether a link has an unlinking or splitting number k, finding a k-component unlink as a sublink, and finding a k-component alternating sublink.

AB - We prove that certain problems naturally arising in knot theory are NP–hard or NP–complete. These are the problems of obtaining one dia-gram from another one of a link in a bounded number of Reidemeister moves, determining whether a link has an unlinking or splitting number k, finding a k-component unlink as a sublink, and finding a k-component alternating sublink.

UR - http://www.scopus.com/inward/record.url?scp=85119576529&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85119576529&partnerID=8YFLogxK

U2 - 10.1090/btran/71

DO - 10.1090/btran/71

M3 - Article

AN - SCOPUS:85119576529

SN - 2330-0000

VL - 8

SP - 420

EP - 441

JO - Transactions of the American Mathematical Society Series B

JF - Transactions of the American Mathematical Society Series B

IS - 15

ER -

NP–HARD PROBLEMS NATURALLY ARISING IN KNOT THEORY

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this