On Computational Complexity of Computing Jones Polynomials

结理论是拓扑学的一个子领域。结是嵌入在R^3中的简单（非自相交）封闭曲线。更一般地说，人们可以研究联系。一个连杆是一个有限的集合不相交嵌入结。结理论的研究已经在其他领域，如生物学、化学和物理学中取得了许多重要的进展。为了对连杆进行分类和表征，结理论中定义了各种不变量，并对其进行了深入的研究。琼斯多项式是一个有用的不变量。众所周知，计算琼斯多项式通常是#P-hard。在最坏的情况下，预计需要指数级的时间。近年来，人们认识到计算具有合理约束的连杆的琼斯多项式的重要性。在这个项目中，我们证明了pretzel链路的Jones多项式在O（n^2）时间内是可计算的，其中n是输入Tait图中的边数。此外，我们还提出了一种计算蒙特西诺斯链路琼斯多项式的快速算法。给定具有n条边的蒙特西诺斯图的tail图，我们的算法在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.