np是什么意思呢 p=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不太可能的一个心理原因是，提出数学定理这样的任务通常需要一定程度的创造力，而我们并不指望一个简单的计算机程序具有这种创造力。

文章插图
我们欣赏维尔斯关于费马最后定理的证明以及牛顿，爱因斯坦，达尔文，沃森和克里克的科学理论，欣赏金门大桥和金字塔的设计，有时甚至是赫尔克里·波洛和马普尔小姐对谋杀案的分析。
正是因为他们似乎需要一个飞跃，这不是每个人都能做到的，更不用说简单的机械设备了——阿维·威格森
以上的观点让我们开始讨论人类大脑的本质。虽然科学离理解大脑的机制还很遥远，但物理定律控制着它的行为。因此，就像其他自然过程一样，大脑是一种高效的计算设备。
因此，任何解决任何问题的方法只要被大脑识别，就可以被有效地识别。因此，P=NP可能意味着大脑有能力以同样的效率解决这些问题。
如果P = NP，那么任何人类或计算机都将拥有传统上被认为是神的那种推理能力，这似乎很难接受。
对于大多数人来说，像怀尔斯对费马最后定理的证明或爱因斯坦的相对论这样的惊人发现可以由一个没有头脑的机器人产生是不可能的，因为他们都有一个强烈的观点，即创造力对于获得这样的见解是绝对必要的。

文章插图
如果P=NP，那么这个世界将是一个与我们通常假设的完全不同的地方。每个能欣赏交响乐的人都会是莫扎特。”——Avi Wigderson
【np是什么意思呢 p=np是数学问题吗】复杂性理论家普遍认为P不等于NP，这样一个美丽的世界是不可能存在的。2000年，克莱数学研究所将P与NP问题列为数学中七个最重要的开放问题之一，并为能证明P是否等于NP的问题提供了100万美元的奖金。