40年来，计算机科学家的寻找答案并不存在
关注微信：DuoDaaMath 每天获得更多数学趣文
作者， Kevin Hartnett，南卡罗来纳作家。
翻译，黑大帅，哆嗒数学网翻译组成员。
40年来，计算机科学家一直试图寻找一个更快的方法来做一个重要的被称为“编辑距离”（edit distance）的计算。两名在麻省理工学院的研究人员由于开创性的工作，知道了失败的原因实际上是因为不可能创建一个更快的方法。
编辑距离是一个容易理解以及实用的东西。想象你有两个数列，并想知道它需要多少步来把其中一个转换成另一个。在这个转换中，您可以添加一个数字，删除一个数字，或替换一个数字成另一个。例如，你有数据字符串“1234”和“2345”，把第一个数列变成第二个需要2步——删除“1”，添加一个“5”。
这个转换所需要的步骤数就是编辑距离。这是一个非常酷炫，也非常有用的概念。生物学家在比较不同生物的染色体时使用的距离都是编辑距离。染色体大体上是一长串的数据—由A，G，T，C组成的DNA的数列。通过计算两种生物的染色体之间的编辑距离，生物学家可以估计早在进化时间的生物彼此差异。
编辑距离虽然很有用的，但计算起来也很耗费时间。目前的计算方法，被称为菲舍尔-瓦格纳算法。它是40年前发展起来的，大致方法是将数据放在一个网格里。其中一个字符串摆放在第一行，另一个竖过来摆放在第一列，随着算法进行，填充对角线，计算变化的次数。
菲舍尔-瓦格纳算法是一种密集型的计算方法，计算机科学家称之为“平方复杂度”，在一般情况下，这意味着当数据字符串的长度上升了一点点，所需的步骤的数目，相比长度会上升很多。例如，如果你有2个数列，每个数列包含10个数字，它需要100个操作（10的平方）来计算编辑距离。但是，如果你有2个序列，每个有100个数字，它需要你10000个操作（100的平方），相比之下。数列的长度上升了一点点（只有90）。操作的数量上升了很多（9900）。
编辑距离的计算只需要平方时间的事实，对基因组学有很大的影响。人类的染色体包含约3000000000个碱基对。计算两个染色体之间的编辑距离需要3000000000的平方次操作（欣赏一下有多大，在9后面写18个零）。麻省理工学院的彼得亚雷·因迪克解释说这个操作的数量，是“不可行的”。也就是说，我们最好的电脑用了很长一段时间仍然不会产生一个答案。
因为人类染色体之间的编辑距离的计算是不可行的，生物学家必须近似计算。他们希望更快的方法，但是因迪克和他的合著者，麻省理工学院毕业的学生巴克斯，最近发现不可能创造一个更快的方法。他们是“很难做到”或者“我们必须首先提高我们的技术”，他们的意思是，“通过数学的规律，我们无法做到。”
因迪克和巴克斯在六月的波特兰，俄勒冈州的理论计算年会上展示了自己的成果。很难描述他们是如何证明这是不可能的，但他们的方法是很容易理解的。在计算机科学中，最著名的开放式问题是对NP-问题的研究。这是一个超大型的问题。首先证明它的人会获得数百万美元的奖金，而且国际新闻会争相报道。要不是大多数几乎所有的计算机科学家都认为NP-问题不等于P问题。因迪克和巴克斯采用了一个聪明的策略，他们说明，为了更快地计算编辑距离，更强的变形的P等于NP问题必须是正确的。因为大多数人都相信，这种变形的P等于NP问题是不正确的，它说明了几乎肯定没有办法真正能提升菲舍尔瓦格纳算法的效率。
因迪克和巴克斯的结果受到计算机科学家们的一致欢迎，他们现在可以不用为了找到一个不存在的更快的方法而拿脑袋撞墙。
麻省理工学院的计算机科学家阿伦森·史葛说：“我记得15年前我还是一个学生的时候，我想知道是不是能用平方复杂度以内的算法击败编辑距离。多亏了巴克斯和因迪克，我们第一次知道不能。”
对于因迪克来说，他最近的工作中心也转移到其他问题上。像其他计算机的数百名科学家一样，他花了几年的找一个更快的方法来计算编辑距离未果。现在，他说，“我将不再试图解决这个问题。”
关注微信：DuoDaaMath 每天获得更多数学趣文
评论已关闭