The Computational Complexity of Knot Genus and Spanning Area
The Computational Complexity of Knot Genus and Spanning Area
复制标题
结属和跨越面积的计算复杂度
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
W. Thurston
中科院分区：
文献类型：
--
作者：
I. Agol;J. Hass;W. Thurston
我们研究三维拓扑学和几何学中一些问题的计算复杂性。我们表明，确定三维流形中一个纽结的亏格的界的问题是NP完全的。利用类似的思路，我们表明，判定一个度量多面体三维流形中的一条曲线是否界定一个面积小于给定常数C的曲面是NP难的。
We investigate the computational complexity of some problems in three-dimensional
topology and geometry. We show that the problem of determining a bound on the genus of a
knot in a 3-manifold, is NP-complete. Using similar ideas, we show that deciding whether a
curve in a metrized PL 3-manifold bounds a surface of area less than a given constant C is
NP-hard.