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

　　北京时间7月4日消息，P对NP问题一直是全球七大数学难题之一。美国马萨诸塞州克雷数学研究所为此设立了专项奖金，能够证明或反驳这一猜想可以获得100万美元的奖金。但如果有人能够证明P实际上等于NP，也许根本不需要再重视奖金问题，因为他可以轻易把全世界的比特币收入囊中。
　　正如理论计算机科学家斯科特阿伦森（ScottAaronson）上周在新墨西哥州洛斯阿拉莫斯国家实验室（LosAlamosNationalLab）发表的演讲那样，证明PNP将开启一些有趣的可能性。P与NP的重要性主要在于它对计算的影响。
　　P指的是计算机一直在解决的问题，从简单的两位数字相乘到更复杂的任务，比如浏览互联网等。当一个问题变得越来越复杂时，解决它所需的时间就会以多项式时间增长，多项式是一个具有幂和系数的数字（比如n2）。如果一个问题在n2时间内解决，并且把输入的规模增加一倍，那么解决问题所需的时间就会增加四倍。
　　阿伦森幽默地表示，如果有人证明PNP，他们应该做的第一件事就是挖走2000亿美元的比特币。第二件事是解决所有其他千禧年奖难题。
　　要理解这一点，人们必须明白计算机是解决问题的设备，根据计算机科学之父艾伦图灵（AlanTling）提出的原则，抽象为物理计算设备可读的代码。解决问题需要大量的步骤和一定的时间，随着问题的增加，所需的时间也会增加。
　　然而，在许多问题中，人们可以确定一个给定的答案在多项式时间内是正确的，但实际上，在多项式时间内得到这个答案可能性却是开放的，也许可以，也许不可以。这些问题称为不确定多项式时间或NP问题。数独就是一个NP问题，很难解决但却很容易核对结果。今天的另一个重要例子是分解质数。就目前而言，把一个很大的数分解成质数需要很长时间，比多项式时间还要久，但是检查答案是否正确就如同把所得的数字相乘一样简单。事实上，这正是现代加密技术的基础，现代加密技术依赖于生成易于验证但难以破解的安全密钥。
　　新的数学证明已经发现，并可能继续找到这些NP问题的P解。P对NP问题实际上是指，是否每个NP问题都有一个P解，或者是否存在通过P绝对不能解决的NP问题。虽然PNP看似显而易见，但它并没有经过严格的数学证明。如果能够证明PNP意味着多项式时间算法适用于很多非常重要的计算机问题，届时揭开比特币的神秘面纱显然不再是件难事儿，毕竟比特币挖掘和安全密钥都依赖于难以解决却易于验证的NP问题。
　　量子计算机的数学基础与经典计算机不同，不能保证每一个NP问题都有P解。人们曾经认为，这类计算机可能解决NP问题中最难攻坚的一类，即NP完全问题。如果你能找到这些问题的一个有效解，你就能找到所有NP问题的有效解。这包括旅行推销员问题和许多其他类似的优化问题，但量子计算机并没有达到这种程度。相反，量子计算机可以在较短的时间内（比如采用一个较低的多项式）解决一些P问题，或者将一些NP问题转移到P的量子泛化中，后者被称为BQP或有界误差量子多项式时间问题。