乍看之下，今年夏天计算理论会议上公布的重大消息似乎有些令人失望。四十多年来，研究人员一直试图找到一种更好的方法，用来比较两个任意字符串，例如DNA分子中由化学字母构成的长串字符。应用最广泛的算法速度缓慢，也并不十分巧妙：它沿着两个列表逐步推进，在每一步比较数值。如果能找到计算这种“编辑距离”的更好方法，研究人员就能快速比较完整基因组或大型数据集，计算机科学家也将拥有一个强大的新工具，用来尝试解决该领域的其他问题。
然而，在 ACM Symposium on Theory of Computing上发表的论文中，麻省理工学院的两名研究人员提出了 一个数学证明 ，认为当前最佳算法是“最优的”——换言之，找到计算编辑距离的更高效方法在数学上是不可能的。 《波士顿环球报》 以一则 标题 为家乡研究人员的成就喝彩，标题写道：“四十年来，计算机科学家一直在寻找一个并不存在的解决方案。”
但研究人员还不急于记录死亡时间。仍存在一个重要漏洞。该不可能性结论只有在另一个著名的未经证明的论断也成立时才成立，这一论断即强指数时间假设（SETH）。大多数计算复杂性研究人员都假定情况如此，包括 Piotr Indyk 和 Artūrs Bačkurs （二人均来自麻省理工学院，并发表了编辑距离的研究结果），但SETH的有效性仍是一个未解问题。这使得有关编辑距离问题的报道看起来像马克·吐温去世传闻的数学版本：严重夸大。
媒体对编辑距离的困惑，反映出复杂性理论 本身深处的模糊之处，数学家和计算机科学家试图厘清哪些在计算上可行、哪些 不可行 ，就像深海探险家测绘海沟底部那样。这一算法地貌与真实海床一样广阔，也同样鲜为人知，正如 Russell Impagliazzo（一位复杂性理论学者，曾与 Ramamohan Paturi于1999年首次提出指数时间假设）所言。“这个比喻很贴切，”他说。“海洋就是计算困难性所在之处。我们正在做的，是用更精细的工具测量不同地方的海洋深度。”
如需继续阅读，请前往 Quanta Magazine。发布本文并不意味着世界经济论坛认同其中观点。
如需紧跟 Agenda 动态，请 订阅我们的每周时事通讯。
作者：John Pavlus是一位作家兼电影制作人，其作品曾见于《科学美国人》、《彭博商业周刊》以及《最佳美国科学与自然写作》系列丛书。
图为一幅插图，展示二进制代码投射在华沙一间办公室里一名手持笔记本电脑的男子身上。REUTERS/Kacper Pempel
