The computational complexity of knot genus in a fixed 3-manifold
The computational complexity of knot genus in a fixed 3-manifold
复制标题
固定3流形中结亏格的计算复杂度
DOI：
10.1112/plms.12500
复制
发表时间：
2023
影响因子：
1.8
通讯作者：
Lackenby M
中科院分区：
文献类型：
--
作者：
Lackenby M
我们证明了在一个固定的闭可定向三维流形中判定一个纽结是否与一个亏格至多为g$g$的曲面有界的问题是不可NP的。这回答了Agol、Hass和Thurston在2002年提出的一个问题。在此之前，这是已知的有理同调3球，由第一作者的工作。
We show that the problem of deciding whether a knot in a fixed closed orientable 3‐dimensional manifold bounds a surface of genus at most g$g$ is inco‐NP. This answers a question of Agol, Hass and Thurston in 2002. Previously, this was known for rational homology 3‐spheres, by the work of the first author.