论文标题
在3个manifold的边界上确定非简单曲线的合同：计算循环定理
Deciding contractibility of a non-simple curve on the boundary of a 3-manifold: A computational Loop Theorem
论文作者
论文摘要
我们提出了以下问题的算法。给定三角剖分的3个manifold M和A（可能是非简单的）封闭曲线，在M边界上确定该曲线是否在M中缩合。我们的算法在空间多项式中以输入的大小在多项式中运行，并且（因此）在指数时间内（因此）。这是第一种专门为此问题设计的算法。它在文献中隐含的现有界限大大改善了3个manifold中封闭曲线的合同性问题。算法的正确性证明依赖于3个manifold拓扑的方法，尤其是在循环定理证明中使用的方法。作为副产品，我们获得了在多项式空间中运行的循环定理的算法版本，并在指数时间内（因此）。
We present an algorithm for the following problem. Given a triangulated 3-manifold M and a (possibly non-simple) closed curve on the boundary of M, decide whether this curve is contractible in M. Our algorithm runs in space polynomial in the size of the input, and (thus) in exponential time. This is the first algorithm that is specifically designed for this problem; it considerably improves upon the existing bounds implicit in the literature for the more general problem of contractibility of closed curves in a 3-manifold. The proof of the correctness of the algorithm relies on methods of 3-manifold topology and in particular on those used in the proof of the Loop Theorem. As a byproduct, we obtain an algorithmic version of the Loop Theorem that runs in polynomial space, and (thus) in exponential time.
