你可能听说过有名的p和NP的问题。 如果你能证明或反驳那个密码短的方程式，你就能拥有100万美元的财富，甚至更高，达到数千亿美元。 这取决于你的担忧。
p和NP的重要性主要是对计算的影响。 那正好是七个千年奖问题之一，意味着马萨诸塞州剑桥的克雷数学研究所将向哪些证明者和反驳这项声明的人发放一百万美元。 但是，如果证明p实际上等于NP，那么连这100万美元的奖金都不需要。 因为有更多的财富在等待。 正如理论科学家励志薯片(Scott Aaronson )上周在新墨西哥州洛斯阿拉莫斯国家研究所) Los Alamos National Lab的“闷热”礼堂讲座中所解释的那样，P=NP被证明将开启有趣的可能性。
“如果有人证明了P=NP，他们要做的第一件事就是盗取2000亿美元的比特币。 他们需要做的第二件事是解决所有其他千年奖问题。 ”动人的薯片说。
要了解这一点，您需要知道计算机是解决问题的设备，物理计算设备基于Alan Turing提出的原则抽象为可读代码。 解决问题需要很多步骤和一定的时间，随着问题变大，所需时间也会增加。
“p”是计算机解决的问题，用简单的两个数字乘以更复杂的任务，如浏览互联网。 随着问题的复杂性增加，解决它的时间量在“多项式时间”中增加。 其中多项式是具有幂和系数的数字(如n )。 如果问题在n小时内得到解决，输入大小增加一倍，则解决问题所需的时间将增加四倍。
但是，虽然有很多问题可以确认给定的答案在多项式时间内是正确的，但是实际上在多项式时间内可能是不可能得到答案的。 这些被称为“不确定多项式时间”或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完全问题一样复杂。