The Next 350 Million Knots
The Next 350 Million Knots
复制标题
接下来的 3.5 亿节
DOI：
10.4230/lipics.socg.2020.25
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Benjamin A. Burton
中科院分区：
文献类型：
--
作者：
Benjamin A. Burton
在19世纪，将所有素数结按给定的交叉数制表是结理论的基础问题之一，并且在今天仍然令人感兴趣。在这里，我们将表格从16个扩展到19个交叉点，总共有352个152个252个不同的非平凡素数结。制表有两个主要阶段：(1)组合枚举阶段，其中包括生成可证明的充分候选结图集；(2)计算拓扑阶段，包括识别和删除重复的结，并证明所有剩余的结在拓扑上是不同的。在本文中，我们描述了这个过程中许多不同的算法组成部分，它们利用了图论、双曲几何、结多项式、法向曲面理论和计算代数。我们还讨论了在数亿个输入上系统可靠地解决困难拓扑问题的算法工程挑战，尽管这些问题没有已知的可靠快速算法。
The tabulation of all prime knots up to a given number of crossings was one of the founding problems of knot theory in the 1800s, and continues to be of interest today. Here we extend the tables from 16 to 19 crossings, with a total of 352 152 252 distinct non-trivial prime knots. The tabulation has two major stages: (1) a combinatorial enumeration stage, which involves generating a provably sufficient set of candidate knot diagrams; and (2) a computational topology stage, which involves identifying and removing duplicate knots, and certifying that all knots that remain are topologically distinct. In this paper we describe the many different algorithmic components in this process, which draw on graph theory, hyperbolic geometry, knot polynomials, normal surface theory, and computational algebra. We also discuss the algorithm engineering challenges in solving difficult topological problems systematically and reliably on hundreds of millions of inputs, despite the fact that no reliably fast algorithms for these problems are known.
影响因子：
0.7
作者：
.Ilker S. Yuce-Ilker-S.-Yuce-102800584
通讯作者：
.Ilker S. Yuce-Ilker-S.-Yuce-102800584