On computational algorithms of invariatns of links and graphs

本研究的目的是研究结点、链路和图的拓扑不变量的变换算法。我们的研究结果如下：（2003）设L为一个连杆，c为L的一个图的交叉数。我们证明了树状连杆的琼斯多项式是用O(c).2次多项式的O（c^3）次运算来计算的。（2004）构造了一个关于打结问题的交互式证明系统，证明了该问题包含在IP中。因此，解结问题包含在AM和co-AM中。（2004）我们给出了从它们的尾部图中计算2-桥链和封闭3-辫链的琼斯多项式的快速算法。给定一个有n条边的Tait图，这些算法对O(n)次多项式进行O(n)次算术运算，其中n是连接图的交叉点数。（2005）我们给出了从它们的尾部图中计算2-桥链和封闭3-辫链的琼斯多项式的快速算法。给定一个有n条边的尾部图，这些算法在O（n^2log n）时间内运行。（2005）给出了一种从整数序列表中计算蒙特西诺斯链的琼斯多项式的快速算法。给定一个整数序列列表，表示一个有n个交叉点的链接图，该算法运行O(n)次多项式运算。

The purpose of this research is to study alogrithms of cmuting topologizal invariants of knots, links and graphs.Our results are followings:1. (2003) Let L be a link, c the number of crossings of a diagram of L. We showed that the Jones polynomial of an arborescent link is computed with O(c^3) operations of polynomials of degree O(c).2. (2004) We constructed an interactive proof system for the Knotting Problem, and proved that the problem is contained in IP. Consequently, the Unknotting Problem is contained in both AM and co-AM.3. (2004) We gave 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), where n is the number of the crossings of the link diagram.4. (2005) We gave 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 in O(n^2log n) time.5. (2005) We gave 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).