您可能听说过著名的P与NP问题。如果你可以证明或反驳它的密码短方程式，那么你就能拥有一百万美元财富，甚至更多，达数千亿美元，这取决于你的顾虑。
P与NP的重要性主要在于其对计算的影响。它恰好是七个千年奖问题之一，意味着马萨诸塞州剑桥的克莱数学研究所将向哪些证明或反驳该宣告的人颁发100万美元。但是，如果你证明P实际上与NP相等，你甚至已经不需要这100万美元的奖金，因为更多的财富在等着你。正如理论电脑科学家斯科特·亚伦森（Scott Aaronson）上周在新墨西哥州洛斯阿拉莫斯国家实验室（Los Alamos National Lab）的一个“闷热”礼堂的讲座中解释的那样，证明P = NP会开启一些有趣的可能性。
“如果有人证明P = NP，他们应该做的第一件事是窃取2000亿美元的比特币。他们应该做的第二件事是解决所有其他千年奖问题，“斯科特·亚伦森说。
要理解这一点，您需要知道计算机是解决问题的装置，根据Alan Turing提出的原则抽象为物理计算装置可读的程式码。解决问题需要花费很多步骤和一定的时间，随着问题的增大，所需的时间也会增加。
“P”指的是计算机一直在解决的问题，从简单的两个数字乘以更复杂的任务（如浏览互联网）。随着问题的复杂性增加，解决它的时间量在“多项式时间”中增长，其中多项式是具有幂和系数的数字（如n）。如果问题在n时间内是可以解决的，并且你输入的大小加倍，那么解决它所需的时间将增加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相等。如果你成功了，你将至少赚到一百万美元，也许还要多得多。如果你不成功，那么，希望你能带领一个有意义的生活研究计算理论。
在P与NP问题中显示相关复杂性类的图。“P”问题在多项式时间内可解；“NP”问题在多项式时间内可解，在多项式时间内可检查。“NP完全”问题是NP问题，因此找到它们的解决方案可以让您解决每个NP问题。“NP难”问题是至少和NP完全问题一样复杂的问题。
