20世纪80年代的数学谜语终于被解决了-可以用来改进计算机

研究人员认为，他们距离解决20世纪80年代的一个数学谜题还有五年的时间，但实际上，他们在不知情的情况下，几乎已经破解了这个问题。

哥本哈根大学和丹麦技术大学(DTU)的研究人员认为，他们距离解决20世纪80年代的一个数学谜题还有5年的时间。实际上，他们在不知情的情况下，几乎破解了这个问题，刚刚在一篇研究文章中透露了大部分解决方案。这个解决方案可以用来改进未来的手机和电脑。

名副其实的脑筋急转弯。这就是如何在图论学科中安全地描述这个数学问题。哥本哈根大学计算机系和DTU的两位数学家现在已经解决了一个世界上最快、最聪明的人自20世纪80年代以来一直在努力解决的问题。

这两位计算机科学家，UCPH的雅各布·霍尔姆助理教授和DTU的伊娃·罗滕伯格副教授，在提交了一篇研究文章后，在2019年夏天几乎泄露了他们的解决方案，这篇文章成为他们最终解决数学谜题的文章的前奏。

“我们几乎放弃了拿到最后一块碎片和解开谜团。我们认为我们有了一个很小的结果，一个有趣的结果，但没有以任何方式解决问题。雅各布·霍尔姆(Jacob Holm)解释说，他是加州大学计算机科学系(UCPH‘s Department of Computer Science)算法部门BARC的一员，他解释说：“我们估计，充其量还需要五年的工作才能解开这个谜团。”

简单地说，这个难题是关于如何在不让连接这些点的线相交的情况下将图中的多个点连接起来。以及如何通过数学计算--一种算法--对广泛的“图形网络”进行更改，以确保没有任何线相交，而不必从头开始。这些特性可以用来建造巨大的道路网络或计算机的微小内部，在那里电路板上的电路可能不会交叉。

雅各布·霍尔姆自1998年以来一直对这个数学难题感兴趣，但直到两位研究人员通读他们已经提交的研究文章时，答案才被揭晓。与此同时，研究人员听说了一种新的数学技术，他们意识到这种技术可以应用到这个问题上。

“在阅读我们的研究文章时，我们突然意识到解决方案就在眼前。DTU副教授伊娃·罗滕伯格(Eva Rotenberg)说，我们的下一个反应是‘哦，糟了--我们搬起石头砸自己的脚，泄露了解决方案。’

这就是两位研究人员忙于撰写研究论文并整理未解决的细节，以解决霍尔姆自1998年以来一直断断续续地致力于解决的难题的时候。

“我们马不停蹄地写这篇文章，花了五到六个星期。而且，它最终占了80多页，“伊娃·罗滕伯格说。

幸运的是，没有人比他们更快找到解决方案，这两位研究人员能够在主要的理论计算机科学会议上展示他们的结果，这些会议本来打算在芝加哥举行，但最终实际上是在举行。

那么，这个数学难题的解决方案能用来做什么呢？这两位研究人员还不能确定，但他们有一些建议。

“我们的研究是基础研究，所以我们很少知道它最终会被用来做什么。雅各布·霍姆补充道：“即使从一开始，我们就发现应用程序很难想象。”

“在所有电子产品中都可以找到的微芯片和电路板的设计，可能是我们的成果最终得到应用的一个领域。在电路板上绘制导线时，它们绝不能相交。否则，就会发生短路。同样的道理也适用于微芯片，它包含数百万个晶体管，必须有图表。“。

Graph是一种非常简单的结构，用于对可以描述为对象的事物以及它们之间的连接进行建模。图论既是数学领域，又是计算机科学的重要工具。

在此上下文中，图可以由与多条线(边)相关联的多个点(节点、顶点)组成的图来说明。每条边都显示为一条直线(或曲线段)，其中节点作为其两个端点。

动态图中有两种更新：一种是删除边，另一种是插入新边。这两个操作必须由用户进行，而算法始终跟踪网络的绘图。这就是研究人员已经找到配方的算法。

参考文献：Jacob Holm和Eva Rotenberg所著的“多对数时间内的全动态平面性测试”，2019年12月10日，“计算机科学&>数据结构和算法”(Computer Science&>Data Structures and Algorithms)。Arxiv：1911.03449