NP-hard problems naturally arising in knot theory
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2018
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913431533125632 |
|---|---|
| author | Koenig, Dale Tsvietkova, Anastasiia |
| author_facet | Koenig, Dale Tsvietkova, Anastasiia |
| contents | We prove that certain problems naturally arising in knot theory are NP--hard or NP--complete. These are the problems of obtaining one diagram 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1809_10334 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | NP-hard problems naturally arising in knot theory Koenig, Dale Tsvietkova, Anastasiia Geometric Topology We prove that certain problems naturally arising in knot theory are NP--hard or NP--complete. These are the problems of obtaining one diagram 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. |
| title | NP-hard problems naturally arising in knot theory |
| topic | Geometric Topology |
| url | https://arxiv.org/abs/1809.10334 |