百年纽结问题迎来突破

在现实生活中，我们对纽结并不陌生，解开一个纽结几乎是我们常常需要做的事，比如解开缠绕的电源线、耳机绳等等等等。然而从数学的角度看，解开纽结这一问题并不像看起来那么简单，它涵盖着许多复杂的抽象数学概念，涉及到高维空间中的几何问题。

纽结在数学上的定义是存在于三维空间中的简单闭曲线。简单来说，它指的是当我们将一根绳子随意打成结，然后再将成结后的绳子的两端粘在一起，得到的就一个数学意义上的纽结。这意味着，它是一个闭合的、不能被解开成一个简单的环的曲线。假如将这样的纽结放置在桌面上，再从上向下俯视纽结，那么呈现在你眼前的就是纽结的平面投影。在数学中，这种具有多个交叉的图形被称为纽结图。

图片 图中所示为三叶形纽结的纽结图。| 图片素材来源：Marnanel / Wikipedia

在数学概念中，无论一个纽结在乍看之下多么繁杂，只要它可以通过移动绳结而被解开成为一个简单的环，那么就可以被称为平凡纽结（unknot）。

图片 图中所示的两个复杂纽结都是平凡纽结，它们都可以最终被解开成为一个圆环。| 图片素材来源：maths.ox.ac.uk

一直以来，有这样一个与平凡纽结有关的问题困扰着许多数学家，那就是对于任意一个给定的纽结图，要如何确定它所代表的是否为平凡纽结。在近100年的时间里，许多数学家和计算机科学家都致力于寻找一个能够有效用于判断一个给定纽结是否为平凡纽结的算法。

这个问题最早是由数学家马克斯·德恩（Max Dehn）于1910年提出的；1954年，阿兰·图灵（Alan Turing）在《可解决的和不可解决的问题》一文中再次提到这个问题，在论文中，图灵写道：“目前还没有系统的方法可以判断两个纽结是否相同。”

直到1961年，德国数学家沃尔夫冈·哈肯（Wolfgang Haken）才为如何确定一个纽结是否是为平凡纽结提供了首个算法。在接下来的几十年间，数学家通过使用各种各样的技术，发展出了许多不同的算法来解决这个问题。然而，这些算法都有一个共同的问题，那就是当纽结趋向于复杂，算法所需的计算时间会显著增加。

一个纽结的复杂程度由它所含有的交叉数（n）来决定。要判断一个纽结是否为平凡纽结，其实所要判断的就是这个纽结中的交叉数是否可以降至为0。对于已存在的算法来说，每当一个给定的纽结的交叉数增加一个，判断它是否是平凡纽结所需花费的时间就要翻倍。

如此一来，这就留下了这样一个问题：我们能在多项式时间（p(n)）内解决平凡纽结的识别问题吗？在这里，多项式时间意味着算法的运行时间可由多项式p(n)给出，而p(n)的大小取决于交叉数n的多少。近十年来，从事这类研究的数学家大多得出的结论是——平凡纽结的识别问题属于NP类问题，即那些当答案为“是”时，存在一个有效的证明来表明“答案为是”的问题。

现在，牛津大学的数学家Marc Lackenby找到了一种算法，能比以往任何算法都更快判断一个纽结是否为“平凡纽结”。这种算法可以在所谓的“准多项式时间（quasi-polynomial time）”，判断出一个交叉数为n的纽结图所代表的的纽结是否是平凡纽结。

Lackenby的算法依赖于使用分层（hierarchy）的概念来证明一个纽结是否为平凡纽结。这种算法可以在n^{c·log(n)}步之内，判断出一个有n个交叉点的纽结图是否是平凡纽结。这里的c代表着准多项式时间，它只比多项式时间稍慢一点，与之前的最好结果相比，是一次重大的进步。

其实，研究一个纽结是否为平凡纽结的意义不仅在于满足了数学家们的好奇心，它还有着许多非常实际且重要的应用。例如在生物研究中，对纽结的理解可以帮助研究人员更好地了解DNA是如何在细胞内缠绕的，再比如对一些包括流体、液晶、聚合物分子、蛋白质等物理系统在内的研究中，对纽结的性质的更好理解也至关重要。

#创作团队：

文：佐佑

图：雯雯子

#参考来源：

https://www.maths.ox.ac.uk/node/38304

https://www.newscientist.com/article/2266995-mathematician-makes-breakthrough-on-100-year-old-problem-about-knots/

http://people.maths.ox.ac.uk/lackenby/quasipolynomial-talk.pdf

#图片来源：

封面图：Clker-Free-Vector-Images / Pixabay