Deciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP-complete. In this paper we determine the parameterized complexity of this problem with respect to a natural parameter called defect. Roughly speaking, it measures the efficiency of the moves used in the shortest untangling sequence of Reidemeister moves. We show that the II- moves in a shortest untangling sequence can be essentially performed greedily. Using that, we show that this problem belongs to W[P] when parameterized by the defect. We also show that this problem is W[P]-hard by a reduction from Minimum axiom set.


翻译:确定结图能否与一定数量的移动( 作为输入的一部分) 脱钩( ) 已知为 NP 完成 。 在本文中, 我们确定这个问题对于称为缺陷的自然参数的参数复杂性 。 粗略地说, 它测量 Reidemeister 移动中最短的未切换序列中使用的移动效率 。 我们显示, 以最短的不切换序列的 II 移动基本上可以贪婪地进行 。 使用它, 我们显示这个问题在标注缺陷时属于 W [P] 。 我们还显示, 这个问题在最小值设置的减值中是 W [P] 硬的 。

0
下载
关闭预览

相关内容

【干货书】计算机科学家的数学,153页pdf
专知会员服务
170+阅读 · 2021年7月27日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【泡泡一分钟】基于表面的自主三维建模探索
泡泡机器人SLAM
9+阅读 · 2019年9月10日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2022年1月11日
Arxiv
3+阅读 · 2018年1月31日
Arxiv
3+阅读 · 2017年12月14日
VIP会员
相关VIP内容
【干货书】计算机科学家的数学,153页pdf
专知会员服务
170+阅读 · 2021年7月27日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
【泡泡一分钟】基于表面的自主三维建模探索
泡泡机器人SLAM
9+阅读 · 2019年9月10日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员