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

发表于 5年以前 | 总阅读数：583 次

正如理论计算机科学家斯科特·阿伦森（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或“有界误差量子多项式时间”问题。