如果你解决了这个数学问题，你就可以窃取世界上所有的比特币

显示P vs NP问题中相关复杂性类别的K线走势图。 “P”问题在多项式时间内是可解的; “NP”问题可能在多项式时间内可解，并且可在多项式时间内检查。 “NP完全”问题是NP问题，因此找到解决方案可以解决每个NP问题。 “NP难”问题至少与NP完全问题一样复杂。 Phew.Graphic：Behnam Esfahbod（Wikimedia Commons）

您可能听说过著名的P与NP问题。如果你可以证明或反驳它的密码短方程式，那么你的财富就会高出一百万美元 – 甚至可能更富有数十亿美元，这取决于你的顾虑。

P与NP的重要性主要在于其对计算的影响。它恰好是七个中的一个 千年奖问题，意思是 克莱数学研究所 马萨诸塞州剑桥市将向那些设法证明或反驳该声明的人颁发100万美元。但是，如果你证明P实际上与NP相等，你甚至不需要100万美元的奖金。正如理论计算机科学家斯科特·亚伦森（Scott Aaronson）上周在新墨西哥州洛斯阿拉莫斯国家实验室（Los Alamos National Lab）的一个闷热的礼堂举行的讲座中解释的那样，证明P = NP会开辟一些有趣的可能性。

“如果有人证明P = NP，他们应该做的第一件事是窃取2000亿美元的比特币。他们应该做的第二件事是解决所有其他千年奖问题，“Aaronson说。

要理解这一点，您需要知道计算机是解决问题的设备，根据Alan Turing提出的原则抽象为物理计算设备可读的代码。解决问题需要花费很多步骤和一定的时间，随着问题的增大，所需的时间也会增加。

“P”指的是计算机一直在解决的问题，从简单的两个数字乘以更复杂的任务（如浏览互联网）。随着问题的复杂性增加，解决它的时间量在“多项式时间”中增长，其中多项式是具有幂和系数的数字（如n2）。如果问题在n2时间内是可以解决的，并且你输入的大小加倍，那么解决它所需的时间将增加4倍。

然而，存在许多问题，其中可以确定给定答案在多项式时间内是正确的，但实际上在多项式时间内获得该答案可能是也可能是不可能的。这些被称为“不确定多项式时间”或NP问题。数独是一个NP问题 – 难以解决，易于检查。今天另一个重要的例子是将大数字分解为素数。至少现在，需要很长的时间 – 比多项式时间慢 – 将非常大的数字计入质数，但检查答案是否正确就像将结果数乘以一样简单。实际上，这个确切的想法是现代加密的基础，它依赖于生成易于验证但难以破解的安全密钥。

更新的数学证明已经发现并可能继续找到解决这些NP问题的P解决方案。 P与NP问题询问每个NP问题是否都有P解，或者是否存在一些在P中绝对无法解决的NP问题。看起来很明显P不等于NP，但它并不严格经过数学证明。如果您碰巧证明P确实等于NP，那么您还将证明存在多项非常重要的计算机问题的多项式时间算法。你可以让自己非常富有 – 比特币挖矿和安全密钥依赖于难以解决，易于检查的NP问题。

量子计算机基于与经典计算机不同的数学，不能为每个NP问题提供P解决方案。曾经有人认为他们可以解决最难的一类NP问题，称为NP完全问题。如果您能找到有效的解决方案，您将能够找到所有NP问题的有效解决方案。这包括 旅行推销员问题 以及许多其他类似的优化问题。但量子计算机 没有辜负这种炒作。相反，量子计算机可以在更短的时间内解决一些P问题（例如，使用较低的多项式）或将一些NP问题移动到P的量子泛化中，称为BQP或“有界误差量子多项式时间”。

因此，去那里尝试证明P是否与NP相等。如果你成功了，你将至少赚到一百万美元，也许还要多得多。如果你不成功，那么，希望你能带领一个有意义的生活研究计算理论。