On computational complexity of computing polynomial invariants of links

我们研究了计算环的多项式不变量的计算复杂性。我们还研究了结点是否解开问题的计算复杂性和辫子共轭问题的计算复杂性，给出了由2-桥环和闭3-辫环的Tait图计算Jones多项式的快速算法。给定一个有n条边的Tait图，这些算法的O(N)次多项式的算术运算为O(N)，即O(n^2logn)时间，其中n是链图的交叉点的个数。我们还给出了从整数序列列表计算Montesinos链的Jones多项式的快速算法。给出一个表示具有$n$交叉点的链接图的整数序列列表，该算法对O(N)次多项式进行O(N)次运算，构造了一个关于结点问题的交互式证明系统，并证明了该问题包含在IP中.N股辫子的共轭问题是如下判定问题：给定两条辫子V，W，确定是否存在一个辫子C使得CV等价于WC。我们证明了辫子的共轭问题存在于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.