np是什么意思呢 数学中的最著名的难题P=NP(3)

np是什么意思呢

RSA-2048有617位十进制数字(2048位)。它是RSA数字中最大的，因式分解获得的现金奖金最高，为20万美元。除非在不久的将来在整数因子分解或计算能力方面取得重大进展，否则RSA-2048在许多年内可能无法分解。

但是，如果P=NP，则最后一个假设是错误的。为什么？如果P等于NP，那么质因数分解问题在P中，这意味着它可以被有效地解决。

因此，一旦找到这样一个算法，任何公钥都可以在合理的时间内解密，而不需要私钥，这使得整个RSA密码系统完全崩溃，至少在理论上如此。

但是P=NP的负面影响与它所具有的潜在好处相比，是无关紧要的。在数学、优化、人工智能、生物学、物理学、经济学和工业领域中，确实存在着数以千计的NP问题，这些问题都是出于不同的需要而自然产生的，而有效的解决方案将使我们在许多方面受益。

证明P=NP将意味着所有这些难题都可以在多项式时间内解决，这将导致在那些卓越的算法之后进行大规模的智力追求。一旦发现，这些算法将有可能推动人类的进步，远远超出我们的掌握。

Christian Boehmer Anfinsen是1972年诺贝尔化学奖的获得者之一，因为他致力于研究一种小的，耐久的100个氨基酸长的蛋白质核糖核酸酶A的折叠。该蛋白质折叠问题是一个NP问题。

即使这样的结果，与解决NP问题的有效方法在数学本身引起的革命相比，也可能显得微不足道。

以著名的毕达哥拉斯定理为例，该定理阐述了直角三角形的直角边和斜边之间的关系。

这个定理有370个已知的证明。这些证明都是下列决策问题的一个可能的解决方案：“勾股定理是正确的吗?”这个想法可以概括为：

如果T是一个定理，p是它的证明，那么p是决策问题的一个解：“T正确吗？”

数学定理与决策问题之间的这种关系允许我们推广关于P与NP的讨论——如果一个证明的正确性可以在多项式时间内得到验证，那么相应的决策问题就是NP问题（因为证明是对该决策问题提出的解决方案）。

在一个P等于NP的世界里，这样一个决策问题在P中，这意味着它可以用多项式时间来解决。

解决这样一个决策问题本质上就是找到定理T的证明。这可能意味着，在某种程度上，证明一个数学定理并不比检查一个给定证明的正确性难多少。

P = NP可能意味着证明一个数学定理从根本上来说并不比验证其证明的正确性更难。

最后的结论是值得注意的，因为每一个数学证明都可以形式化为一系列定义良好的逻辑陈述，并由计算机程序进行处理，自动验证证明。因此，P = NP意味着证明数学定理可以用一个简单的计算机程序来完成。

“P = NP可以通过允许计算机找到任何定理的形式证明来改变数学，只要这个定理能证明一个合理的长度，因为形式证明可以在多项式时间内很容易地被识别出来。”——斯蒂芬·库克

人们认为P=NP不太可能的一个心理原因是，提出数学定理这样的任务通常需要一定程度的创造力，而我们并不指望一个简单的计算机程序具有这种创造力。