旅行商|P vs. NP 五十年:AI正在解决不可解问题( 五 )

科学和医学
在科学方面,我们通过进行大规模的模拟来理解。例如在探索核聚变的反应过程中,我们就取得了一些不错的结果。研究人员可以应用一种形式化的研究方法,为物理系统创建一个假设,然后使用这个假设,并且不断的使用这个假设进行反应和模拟。如果我们得到的结果和实际不相符,则丢弃模型,并且重新开始。
当我们得到了一个强大的模型之后,我们就可以在物理模拟系统中进行很多实际实验中代价昂贵的测试了。如果P=NP,我们可以使用奥卡姆剃刀方法来创建假设,即找到与数据一致的最小电路。机器学习技术可以沿着这条技术路径前进,使假设的创建自动化。当我们给定数据之后,不论是通过模拟还是真正的实验得到数据,机器学习就可以创建模型来拟合这些数据,达到最佳的匹配。我们可以使用这些模型进行预测,然后就像之前那样测试这些预测。
虽然这些技术使我们能够找到可能遗漏的假设和模型,但是也有可能导致误报。人类通常会趋向于接受有95%置信度的假设(这意味着20个坏假设中只有一个能够通过检验)。机器学习和数据科学工具能够让我们生成假设,这些假设都有着脱离实际建模的风险。这就限制了它的工作范围,比如医学工作者就不能承担这些风险,他们的诊断中如果有这些问题,那会遭到很大的麻烦。生物系统也是一种极为复杂的结构。我们知道人类的DNA形成了复杂的编码,它描述了我们的身体是如何形成的,以及它们执行的功能。但是很可惜,我们目前对其工作原理知之甚少。
在2020年11月30日,谷歌旗下的DeepMind发布了AlphaFold,这是一种基于氨基酸序列预测蛋白质形状和结构的新算法。AlphaFold的预测几乎达到了实际实验构建氨基酸序列的和测量蛋白质形状相同的准确度。但是关于DeepMind是否真正“解决”了蛋白质折叠的问题,还存在一些争议,现在评估其影响还为时过早,但是从长远的角度来看,这可以为我们提供一种新的数字工具来研究蛋白质,来了解它们是如何互相作用,并且了解如何设计DNA来对抗疾病。
超越P和NP问题的思考:国际象棋
NP就像是一个迷宫一样,在任意大小的棋盘上各种操作。数独也是NP完全的问题,它需要从一些正方形中给定的数字设置中求解。但是,当我们问到谁从给定的初始设置中获胜时,我们是不是就没办法给出准确的回答了呢?即使我们有P=NP的前提,它也不一定会给我们一个完美的国际象棋的程序来解决问题,这就像需要设计一个程序,它保证能够让白棋走的这一步,逼迫黑棋走那一步,然后白棋再按照计划走这一步,使得黑棋...,最终是白棋获胜。人们无法单独在P=NP上完成所有这些白棋和黑棋的交替。像这样的游戏往往被称为PSPACE-hard,即很难计算、或使用合理数量的内存,并且在约定的时间之内求解完成的问题。根据规则的精确限制,国际象棋和围棋甚至可能更难。
这不意味着如果P=NP,你就不能得到一个好的国际象棋程序。事实上,在某种程度上,象棋的程序体积越大,其智能程度越高。我们可以找到一种有效的计算机程序,它可以击败所有尺寸稍小的其他程序。同时,即使没有P=NP,计算机在国际象棋和围棋方面也变得非常强大了。1997年,IBM的深蓝击败了当时的国际象棋世界冠军。
此外,机器学习为电脑游戏带来了巨大的进步。我们讨论一下声名大噪的AlphaZero,它是2017年DeepMind开发出来的人工智能程序。