On computational complexity of computing polynomial invariants of links

研究了连杆多项式不变量的计算复杂度。我们还研究了结是否解结问题的计算复杂度和辫子共轭问题的计算复杂度。从2-桥链和3-辫链的尾部图出发，给出了计算它们琼斯多项式的快速算法。给定一个有n条边的Tait图，这些算法对O(n)次多项式进行O(n)次算术运算，即在O（n^2log n）时间内运行，其中n是连接图的交叉次数。给出了从整数序列表中计算Montesinos链的Jones多项式的一种快速算法。给定一个整数序列列表，表示一个有n个交叉点的链接图，该算法运行O(n)次多项式运算。构造了一个关于打结问题的交互式证明系统，证明了该问题包含在IP中。因此，解结问题包含在AM和co-AM中。n-链编织物的共轭问题是如下的判定问题：给定两条编织物V， W，判断是否存在一条编织物C，使得CV等于W C。我们证明了编织物的共轭问题在PSPACE中存在。

We investigate computational complexity of computing polynomial invariants of links. We also investigate the computational complexity of the problem whether a knot is unknotting and the computational complexity of the computational complexity of the conjugacy problem for braids.We give fast algorithms for computing Jones polynomials of 2-bridge links and closed 3-braid links from their Tait graphs. Given a Tait graph with n edges, these algorithms run with O(n) arithmetic operations of polynomials of degree O(n) namely in O(n^2log n) time, where n is the number of the crossings of the link diagram. We also give a fast algorithm for computing Jones polynomials of Montesinos links from lists of integer sequences. Given a list of integer sequences that represents a link diagram with $n$ crossings, this algorithm runs with O(n) operations of polynomials of degree O(n).We construct an interactive proof system for the Knotting Problem, and prove that the problem is contained in IP. Consequently, the Unknotting Problem is contained in both AM and co-AM.The conjugacy problem for the n-strand braids is the following decision problem : Given two braids V, W, determine whether there exists a braid C such that CV is equivalent to W C. We give a proof that the conjugacy problem for braids is in PSPACE.