标题： 一个计算琼斯多项式的并行算法 显示英文标题

标题： A parallel algorithm for the computation of the Jones polynomial

摘要： 纽结、链环和纠缠丝线出现在许多生物学和工程学感兴趣的物理系统中。 对纽结进行分类并测量纠缠对于推进纽结理论以及分析通过实验或人工智能获得的大规模数据都有重要意义。 在此背景下，高效计算拓扑不变量和其他纠缠度量成为一个紧迫的问题。 常见拓扑复杂性度量（如琼斯多项式）的计算对于纽结（或纽结体）图中的交叉数而言是#P困难问题，并且需要指数级的时间。 本文介绍了首个用于精确计算三维空间中开闭简单曲线（或曲线集合）琼斯多项式的并行算法。 该算法能够根据处理器数量按指数级减少计算时间。 我们通过将其应用于纽结以及分子动力学模拟得到的熔融态线性聚合物系统来展示此算法的优势。 该方法具有通用性，可以应用于其他不变量和复杂性度量。 显示英文摘要

摘要： Knots, links and entangled filaments appear in many physical systems of interest in biology and engineering. Classifying knots and measuring entanglement is of interest both for advancing knot theory, as well as for analyzing large data that become available through experiments or Artificial Intelligence. In this context, the efficient computation of topological invariants and other metrics of entanglement becomes an urgent issue. 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 the first parallel algorithm for the exact computation of the Jones polynomial for (collections of) both open and closed simple curves in 3-space. This algorithm enables the reduction of the computational time by an exponential factor 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 could be applied to other invariants and measures of complexity.