40年来,计算机科学家的寻找答案并不存在

 

关注微信:DuoDaaMath 每天获得更多数学趣文

新浪微博:http://weibo.com/duodaa

 

作者, 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 每天获得更多数学趣文

新浪微博:http://weibo.com/duodaa

标签: none

评论已关闭