想把全世界的比特币收入囊中?请解开“P对NP”难题

2019-07-04 13:27凤凰科技 (良弼)

北京时间7月4日消息,“P对NP”问题一直是全球七大数学难题之一。美国马萨诸塞州克雷数学研究所为此设立了专项奖金,能够证明或反驳这一猜想可以获得100万美元的奖金。但如果有人能够证明P实际上等于NP,也许根本不需要再重视奖金问题,因为他可以轻易把全世界的比特币收入囊中。

正如理论计算机科学家斯科特·阿伦森(Scott Aaronson)上周在新墨西哥州洛斯阿拉莫斯国家实验室(Los Alamos National Lab)发表的演讲那样,证明P=NP将开启一些有趣的可能性。P与NP的重要性主要在于它对计算的影响。

“P”指的是计算机一直在解决的问题,从简单的两位数字相乘到更复杂的任务,比如浏览互联网等。当一个问题变得越来越复杂时,解决它所需的时间就会以“多项式时间”增长,多项式是一个具有幂和系数的数字(比如n2)。如果一个问题在n2时间内解决,并且把输入的规模增加一倍,那么解决问题所需的时间就会增加四倍。

阿伦森幽默地表示,“如果有人证明P=NP,他们应该做的第一件事就是挖走2000亿美元的比特币。第二件事是解决所有其他千禧年奖难题。”

要理解这一点,人们必须明白计算机是解决问题的设备,根据计算机科学之父艾伦·图灵(Alan Tling)提出的原则,抽象为物理计算设备可读的代码。解决问题需要大量的步骤和一定的时间,随着问题的增加,所需的时间也会增加。

然而,在许多问题中,人们可以确定一个给定的答案在多项式时间内是正确的,但实际上,在多项式时间内得到这个答案可能性却是开放的,也许可以,也许不可以。这些问题称为“不确定多项式时间”或NP问题。数独就是一个NP问题,很难解决但却很容易核对结果。今天的另一个重要例子是分解质数。就目前而言,把一个很大的数分解成质数需要很长时间,比多项式时间还要久,但是检查答案是否正确就如同把所得的数字相乘一样简单。事实上,这正是现代加密技术的基础,现代加密技术依赖于生成易于验证但难以破解的安全密钥。

新的数学证明已经发现,并可能继续找到这些NP问题的P解。P对NP问题实际上是指,是否每个NP问题都有一个P解,或者是否存在通过P绝对不能解决的NP问题。虽然P≠NP看似显而易见,但它并没有经过严格的数学证明。如果能够证明P=NP意味着多项式时间算法适用于很多非常重要的计算机问题,届时揭开比特币的神秘面纱显然不再是件难事儿,毕竟比特币挖掘和安全密钥都依赖于难以解决却易于验证的NP问题。

量子计算机的数学基础与经典计算机不同,不能保证每一个NP问题都有P解。人们曾经认为,这类计算机可能解决NP问题中最难攻坚的一类,即“NP完全问题”。如果你能找到这些问题的一个有效解,你就能找到所有NP问题的有效解。这包括“旅行推销员问题”和许多其他类似的优化问题,但量子计算机并没有达到这种程度。相反,量子计算机可以在较短的时间内(比如采用一个较低的多项式)解决一些P问题,或者将一些NP问题转移到P的量子泛化中,后者被称为BQP或“有界误差量子多项式时间”问题。

文章价值:
人打分
无价值还可以有价值
相关文章
查看更多
大家都在买广告更多
置顶评论
    热门评论
      全部评论
      竟然没有评论,快来说两句吧...
        取消发送
        软媒旗下人气应用