「P=NP问题」 - 数学pnp问题

本文目录一览：

• 1、怎么理解 P 问题和 NP 问题
• 2、p=np证明了吗
• 3、如果P=NP得到证明将意味着什么?

怎么理解 P 问题和 NP 问题

P的含义是polynomial（多项式的）。

要了解什么是P问题NP问题来自，首先要引入算法和时间复杂度的概念。

算法一般指的是一套用于解决问题的流程。算法要保障结果的正确性和运行效率。

对于时间复杂度，一般指的是运算步骤次数和数据量之360问答间的关系。比如说对于一个算法，如果数据量为n，那么如呼衡状少富市哪委果它的运算步骤次数为2*N^2+2次，我们取最高影响的那一项为N^2。这项是整个算法增长速度最快一项。于是我们把算法复杂度计成O（N^2）。

一般的算法关系如此O（logn）O（n）O(n*logn)O(n^2)等瞎搜还义等

然后若K和C是任模圆意常数，如果C1,则O（C^n）O(1)O(n^k)。反之，若C1，O（C^n）O(n^k)。就好比2的n次方比n的任意阶多项式都增长得快。

P问题指的是一些能够被多项式时间复杂度的算法准确解出的问题。而NP问题是目前为止，尚未发现多项式时间复杂度内算法能够解决的问题。NP问题目前最快也是指数级别的算法时间复杂度。

在当前，我们有时会用近似算法快速解决NP问题。主便陈其害善肉对于近似算法（有时用贪心法，有时用放宽条件的线性规划），我们会得到接近最优解的可行解。比如求一个最大值，我如果用构量果确的是0.9倍近似跟道径吸续齐见夜活连使算法，意味着我的算法产生的结果最小也是最优解的0.9倍。这样可以保障得到的结果校鲜未张足够好。

如果P=NP被证明了，也就是说NP问题都能被多项式时间复杂度解决了，那这将是人类历史的巨大变革。

在目前准确解决NP问题的技巧中，你可以使用决策树算法，算法核心以及动态规划结合图的树分解等技巧。然而，这些算法技巧还不足以把NP问题磨码历放在多项式时间复杂度下面解决。

p=np证明了吗

"pvsnp"被认为是计算机科学领域最为重要的未解决的问题，克雷数学研究所也将这个问题列为7个千禧年数学难题之一，可见其在计算机科学和数学领域的重要性和难度。

不过，P与NP这个命题为何重要，《可能与不可能的边界：P/NP问题趣史》一书就以科普的笔法讲清了P/NP问题的历史、现实意义，普通小白读完这本书应该也能弄懂它的含义。

近年来，也不断有人站出来号称自己证明了p!=np或者p=np，然而结论最终都经不起审核或推敲。在我看来，无论是p!=np或p=np，要想完整给出结论，必然需要构造一个特定的算法才行，也即数学里讲到的构造性证明（一切非构造性的证明都是耍流氓）。

比如你想证明p=np，你得构造出一个特定的算法将某一个NPC问题归约为P的问题；如果你想证明p!=np，你也得构造出一个问题，且能够证明该问题不能在多项式时间内找到问题的解。

如果P=NP得到证明将意味着什么?

而且目测整个欧美学术圈theory组暂时都没什么正事可以做了，大部分和计算复杂性相关领域的研究都失去了意义之前发的什么Godel奖、Nevanlinna奖大多数也都是废纸了，什么Probabilistically Checkable Proof，什么Unique Games Conjecture这些所谓的重要研究都是nonsense了不过数学界的机械化证明目测就要成为主流（这么看其实大部分数学家也要失业了？（我在原答案中不假思索地随手敲出了上面这句话，但实际上这是不对的，即使P=NP也未必是机械化证明成为主流，没有任何证据证明数学命题的证明属于NP范畴，而且就算我们有多项式算法判断一个数学命题的正确与否，so what？根本不能和找到一个证明的重要性和意义相提并论。然而我意识到我写这句话是受到了很多其他科普文章的影响，所以我现在觉得解释一下这件事情很重要，面这句话是不对的，没有任何证据表明判断数学命题正确与否属于NP范畴，更何况判断一个数学命题正确与否根本比不上找出一个证明上面这句话是不对的，没有任何证据表明判断数学命题正确与否属于NP范畴，更何况判断一个数学命题正确与否根本比不上找出一个证明）当然以上都是相关专业领域，对于普通民众来说，说不定人类就要进入个新时代了我也很难想象以后的生活，毕竟信仰崩塌了再重建是非常辛苦的。

本文链接：http://www.gs5000.cn/a/2332.html