Jones polynomial of knots formed by repeated tangle replacement operations (Q837637)

The paper under discussion deals with the computational complexity theory of the Jones polynomial of knots and links in the three dimensional sphere. It is known that the computation of the Jones polynomial of an alternating link is \(\#P\)-hard [\textit{F. Jaeger, D. L. Vertigan} and \textit{D. J. A. Welsh}, Math. Proc. Camb. Philos. Soc. 108, No.~1, 35--53 (1990; Zbl 0747.57006)]. The authors construct a large family of knots by tangle replacement operations starting with a simple diagram \(D_0\). Let \(k\) be a constant and suppose that \(D_m\) is an \(n\)-crossing diagram obtained from a simple diagram \(D_0\) by \(m\) tangle replacement operations involving the tangles \(\Gamma_1,\dots,\Gamma_{m}\). The main result of the paper is that the Jones polynomial of \(D_{m}\) can be computed in time \(O(n^{k})\) if \(D_0\) and all the tangles \(\Gamma_1,\dots,\Gamma_{m}\) have at most \(k\) crossings. A consequence is that the Jones polynomial of an \(n\)-crossing Montesinos link can be computed in \(O(n^2)\) time.