NP–hard problems naturally arising in knot theory
NP–hard problems naturally arising in knot theory
复制标题
纽结理论中自然出现的 NP 难题
DOI：
10.1090/btran/71
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tsvietkova, Anastasiia
中科院分区：
文献类型：
--
作者：
Koenig, Dale;Tsvietkova, Anastasiia
我们证明了在纽结理论中自然产生的某些问题是NP-难的或NP-完全的。这些问题是：在有限的Reidemister移动次数中从链路的另一个图获得一个图，确定一个链路是否具有断开链接或分裂数，找到一个分量断开链接作为子链接，以及寻找一个分量交替的子链接。参考文献
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, finding a-component unlink as a sublink, and finding a-component alternating sublink. References
登录
查看更多内容
DOI：
--
发表时间：
2002
期刊：
影响因子：
--
作者：
I. Agol;J. Hass;W. Thurston
通讯作者：
W. Thurston
雷德迈斯特移动的上限
影响因子：
1.7
作者：
A. Coward;M. Lackenby
通讯作者：
M. Lackenby
解开结所需的雷德迈斯特动作次数
影响因子：
3.9
作者：
J. Hass;J. Lagarias
通讯作者：
J. Lagarias
库尔特·雷德迈斯特
DOI：
--
发表时间：
2016
期刊：
Gottinger Jahrbuch
影响因子：
--
作者：
T. Dieck
通讯作者：
T. Dieck
分割链接的 Reidemeister 移动次数
DOI：
--
发表时间：
2005
期刊：
Mathematische Annalen 332
影响因子：
--
作者：
Chuichiro Hayashi;Chuichiro Hayashi;Chuichiro Hayashi
通讯作者：
Chuichiro Hayashi