A parallel algorithm for the computation of the Jones polynomial - Kasturi Barkataki; Eleni Panagiotou (Proceedings of the National Academy of Sciences, 2026)
Knots, links, and entangled filaments appear in many physical systems in biology and engineering and their structural complexity is related to their function. In the context of emerging AI capabilities in predicting new physical structures, as well as in assisting mathematical proofs, the efficient computation of topological invariants and other metrics of entanglement becomes a considerable barrier to scientific advances. The computation of common measures of topological complexity, such as the Jones polynomial, is #P-hard and of exponential time on the number of crossings in a knot(oid) (link(oid)) diagram. In this paper, we introduce a parallel algorithm for the exact computation of the Jones polynomial for (collections of) both open and closed simple curves in 3-space. We prove that this algorithm enables the exponential reduction of the computational time depending on the number of processors. We demonstrate the advantage of this algorithm by applying it to knots, as well as to systems of linear polymers in a melt obtained from molecular dynamics simulations. The method is general and might be applicable to other invariants and measures of complexity.