为了探索一个尚未探索的难题空间研究人员扮演了魔鬼的代言人

奚程剑
摘要在计算机科学中,图着色问题是一个经典问题。受地图着色问题的启发,它问:给定一个由链接连接的节点网络,您需要为每个节点着色的最少颜色数量是多少,以便没有链接连接两个相同颜色的链接?对于少量的颜色和链接,寻找解决方案很简单:只需尝试所有可能的组合。但是随着链接的增加,问题变得更加受限——直到,如果链接太多而颜色不够,则可能根本不存在...

音频解说

在计算机科学中,图着色问题是一个经典问题。受地图着色问题的启发,它问:给定一个由链接连接的节点网络,您需要为每个节点着色的最少颜色数量是多少,以便没有链接连接两个相同颜色的链接?对于少量的颜色和链接,寻找解决方案很简单:只需尝试所有可能的组合。但是随着链接的增加,问题变得更加受限——直到,如果链接太多而颜色不够,则可能根本不存在解决方案。

“然后有这些迷人的中间区域,在那里可能有解决方案,但很难找到-另一个可能没有,但很难证明没有,”居民博学者克里斯摩尔说SFI教授。他说,这意味着传统的问题解决算法无法找到它们。例如,如果从随机着色开始,并且只是开始翻转节点的颜色,则它不会找到这些隐藏的解决方案之一。

在2021年学习理论会议上发表的一篇新论文中,摩尔和他的合作者描述了一种用这种隐藏解决方案构建问题的新方法。该小组包括数学家JessBanks,他是前SFI本科生和学士后实习生,现在正在攻读博士学位。在加州大学伯克利分校。

他们通过扮演某种数学恶魔的拥护者的角色来解决这个问题。他们不是解决问题,而是编造新的、复杂的问题——解决方案隐藏在其中。“我们摘掉了求解者、解决方案寻找者的白帽子,而戴上了设计棘手问题的人的黑帽子——几乎就像密码学,”摩尔说。“解决方案是隐藏的。”

摩尔说,研究人员设计了一种巧妙的方法来隐藏解决方案。而当他们将这些问题交给解决问题的算法时,这些算法就变得空洞了。“如果我们能够创造许多算法无法解决的问题,甚至判断是否有解决方案,”摩尔说,“那么我们就有强有力的证据表明我们已经找到了这些问题难以解决的区域。”

该论文包括一个定理,证明多个算法族无法找到这些生成问题的解决方案。这意味着研究人员比以往任何时候都更接近于确定这个“硬”区域的相变边界,在这个区域很难找到解决方案——或者证明没有解决方案。

摩尔说,精确识别问题的持续努力源于物理学中的猜想,这些猜想询问系统如何在受到更多约束时发生变化。

“我们的冒险,”他说,“是将物理学中的这些猜想和计算转化为数学证明。”他说,推动该领域向前发展的唯一方法是利用数学、物理学和计算机科学工具的重叠优势。

标签:

免责声明:本文由用户自主上传,版权归原作者所有,若有来源标注错误或侵犯了您的合法权益,请与本网联系,我们将及时更正、删除,谢谢您的支持与理解。