On Computational Complexity of Computing Jones Polynomials

纽结理论是拓扑学的一个分支。纽结是嵌入R^3中的简单（非自相交）闭合曲线。更一般地说，人们可以研究链接。链接是不相交嵌入的结的有限集合。关于纽结理论的研究在生物学、化学和物理学等其他领域取得了许多重要进展。纽结理论中定义了各种不变量，并对它们进行了深入的研究。琼斯多项式是一个有用的不变量。众所周知，计算琼斯多项式通常是P-困难的。预计在最坏情况下需要指数时间。最近，人们已经认识到，它是重要的，以合理的限制，计算琼斯多项式的链接。在这个项目中，我们表明，琼斯多项式的pretzel链接是可计算的O（n^2）时间，其中n是在输入Tait图的边的数量。此外，我们提出了一个快速算法计算Montesinos链路的琼斯多项式。给定一个有n条边的Montesinos图的Tait图，我们的算法在O（n）次多项式中运行O（n）次加法和乘法，即O（n^2log {n}）时间。

Knot theory is a subfield of topology. A knot is a simple (non-self-intersecting) closed curve embedded in R^3. More generally, one may study links. A link is a finite collection of disjointly embedded knots. Works on knot theory have led to many important advances in other areas, biology, chemistry and physics. For classifying and characterizing links, various invariants have been defined and profoundly studied in knot theory. The Jones polynomial is a useful invariant. It is known that computing the Jones polynomial is generally #P-hard. It is expected to require exponential time in the worst case. Recently, it has been recognized that it is important to compute Jones polynomials for links with reasonable restrictions.EIn this project, we showed that Jones polynomials of pretzel links are computable in O(n^2) time, where n is the number of the edges in the input Tait graph. Moreover, we propose a fast algorithm for computing Jones polynomials of Montesinos links. Given the Tait graph of a Montesinos diagram with n edges, our algorithm runs with O(n) additions and multiplications in polynomials of degree O(n), namely in O(n^2log {n}) time.