p等于np，为什么p不等于np

本文目录一览

1，为什么p不等于np
2，对于PNP你们的看法
3，谁能具体介绍一下P vs NP
4，什么是P问题NP问题和NPC问题
5，NP的潜规则
6，什么是PNPNPCNPhard问题

1，为什么p不等于np

因为: 1) n ≠ 1, p≠np; 2) p ≠ 0, p≠np.

只有当p=0时，p=np；或者当n=1时，p=np 因为p有可能不等于0，n也可能不等于1，所以大部分情况下p不等于np

我是来混的 = =np啊~~~~我实在想到了不好的东西 = =

为什么p不等于np

2，对于PNP你们的看法

我们可以这样理解：自己想出答案和确认别人的答案是否正确，何者较容易？我认为P≠NP，对于证明的论文。你可以去网上查询，不过现在这个问题还没有人正确的证明出来，楼主应该知道，P≠NP是数学界七大难题之一。总之，这个问题是非常复杂的。给你举个例子，在一个周六的晚上，你参加了一个盛大的晚会。由于感到局促不安，你想知道这一大厅中是否有你已经认识的人。你的主人向你提议说，你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟，你就能向那里扫视，并且发现你的主人是正确的。然而，如果没有这样的暗示，你就必须环顾整个大厅，一个个地审视每一个人，看是否有你认识的人。生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是，如果某人告诉你，数１３，７１７，４２１可以写成两个较小的数的乘积，你可能不知道是否应该相信他，但是如果他告诉你它可以因式分解为３６０７乘上３８０３，那么你就可以用一个袖珍计算器容易验证这是对的。不管我们编写程序是否灵巧，判定一个答案是可以很快利用内部知识来验证，还是没有这样的提示而需要花费大量时间来求解，被看作逻辑和计算机科学中最突出的问题之一。它是斯蒂文·考克于１９７１年陈述的。

对于PNP你们的看法

3，谁能具体介绍一下P vs NP

惠普实验室的研究员Vinay Deolalikar，一位在理论计算机、随机过程、代数和逻辑方面都有过贡献的研究人员，声称证明了P不等于NP。他的证明目前只有初稿在网络上流传，他在自己的网站上宣称将在近期贴出正式的论文。 P vs NP是克莱研究所的千禧年难题大奖中宣布的7道数学世纪难题中的一道。这7道难题分布在数学的不同分支，任一道难题的解决都被认为会对相应的分支有重大的影响。P vs NP问题属于理论计算机这个数学分支。目前为止，这七道难题中唯一被确认证明的是庞加莱猜想，2006年由俄罗斯数学家格里戈里·佩雷尔曼证明。如果Vinay Deolalikar的证明正确，他将很有可能成为第一位领取千禧年难题百万大奖的人（佩雷尔曼拒绝了百万奖金）。 P vs NP问题，简单地说，就是是否每一个容易验证正确性的问题都能很“快”地计算出来？比如说，要验证一个整数是否整除另一个整数是很“快”的，那么给出一个整数，是否能很“快”找出它的一个因子？这里的“快”在理论计算机中有严格的定义，就是所需时间小于一个关于输入长度的多项式，我们也说这个算法可以在多项式时间内解决这个问题。这里牵涉的是算法的时间复杂度，“快”不是绝对意义上的，只是从级数上（主要是和指数级）的比较。 P的正式称呼是“确定性图灵机多项式时间复杂度”，而NP则是“非确定性图灵机多项式时间复杂度”。在理论计算机中，“判定问题”是这样的一类问题，对于某个输入，我们只需要输出“是”或者“否”作为答案。P和NP都是判定问题所组成的集合。如果对于一个判定问题，存在一个能在多项式时间解决它的算法，那么这个判定问题就在P中。如果对一个判定问题，存在一个算法，对于一个肯定的输入，都有一个“旁证”，而算法可以在多项式时间内利用旁证对这个输入进行正确的肯定判定，那么这个判定问题就在NP中。 P vs NP问题，问的正是P是否等同于NP。我们知道，NP包含P，但是在NP中有一类叫NP-完全的问题，至今都没有算法可以容易地解决它们。如果这些问题中有一个属于P的话，NP就等于P；否则，NP就不等于P。P vs NP问题在理论计算机中占有重要的地位，虽然至今为止还没有人确切证明出P是否等于NP，但是主流的推测是P不等于NP，很多应用算法就是基于这样的假设，而许多加密算法的保密性也是建立在P!=NP的前提上的，比如说著名的RSA。P vs NP问题的解决无论对于理论还是实践都有很大的影响。 Vinay Deolalikar的证明横跨了统计、逻辑、统计物理、计算复杂度等学科。他从一个NP-完全问题——可满足性问题（SAT）——入手，尝试证明没有算法可以容易地解决这个判定问题。他先将问题的解的统计特性与一个逻辑模型联系起来，再利用逻辑模型得到一个对算法计算时间的限制。然后他用统计物理的工具，得到了对一类输入——随机kSAT输入——的解的统计特性，将这个统计特性注入此前的逻辑模型中，他证明了对随机kSAT输入，没有算法在多项式时间内解决可满足性问题，从而证明P不等于NP。现在仍不能确定Vinay Deolalikar的证明是否正确。他已将证明用电子邮件发到数位不同领域的专家手上审核。在惠普实验室他的个人页面上，他发表了一个声明，澄清在网上泄露的证明只是初稿，专家的审核尚未完毕，一个最终的版本会在近期内发布。尽管P vs NP相当困难，此前也有不少人对它进行过失败的尝试，但对于这个来自这个领域研究人员的证明还是有希望的，让我们拭目以待。

谁能具体介绍一下P vs NP

4，什么是P问题NP问题和NPC问题

如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于p问题。p是英文单词多项式的第一个字母。哪些问题是p类问题呢？通常noi和noip不会出不属于p类问题的题目。我们常见到的一些信息奥赛的题目都是p问题。道理很简单，一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。np问题不是非p类问题。np问题是指可以在多项式的时间里验证一个解的问题。np问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。之所以要定义np问题，是因为通常只有np问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白，信息学中的号称最困难的问题——“np问题”，实际上是在探讨np问题与p类问题的关系。很显然，所有的p类问题都是np问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。关键是，人们想知道，是否所有的np问题都是p类问题。我们可以再用集合的观点来说明。如果把所有p类问题归为一个集合p中，把所有np问题划进另一个集合np中，那么，显然有p属于np。现在，所有对np问题的研究都集中在一个问题上，即究竟是否有p=np？通常所谓的“np问题”，其实就一句话：证明或推翻p=np。npc问题的定义非常简单。同时满足下面两个条件的问题就是npc问题。首先，它得是一个np问题；然后，所有的np问题都可以约化到它。证明一个问题是npc问题也很简单。先证明它至少是一个np问题，再证明其中一个已知的npc问题能约化到它这样就可以说它是npc问题了。

1、P问题P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解;P事实上很直观,我们通常在编程中求解的问题大多都是P类问题.比如说排序,找最短路径等.2、NP问题然而有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP?这个问题至今还未解决。NP这个类事实上也很有趣,它并不要求给出一个算法来求解问题本身,而只是要求给出一个确定性算法在多项式时间内验证它的解.3、NP完全问题此外请注意，NP问题不一定都是难解的问题，比如，简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题，你能说他很难解么？刚才说了，现在还不知道是否有P=NP或者P<>NP，但是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信P<>NP，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题（NPC问题，C代表complete）。NP完全问题是求NP中判定问题的一个子类.NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久，cook在1971年找到了第一个NPC问题，此后人们又陆续发现很多NPC问题，现在可能已经有3000多个了。所以，我们一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，但是也不是不可能）。类似哈米尔顿回路/路径问题，货郎担问题，集团问题，最小边覆盖问题（注意和路径覆盖的区别），等等很多问题都是NPC问题，所以都是难解的问题。

5，NP的潜规则

NP问题一个NP－完全的问题具有如下性质：它可以在多项式时间内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。 P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合。令L1和L2是两个问题，如果有一确定的多项式时间算法求解L1，而这个算法使用了一个在多项式时间内求解L2的确定算法，则称L1约化为L2。如果可满足性约化为一个问题L，则称L问题是NP-难度的。如果L是NP难度的且L（－NP，则称L是NP－完全的。 NP并不是NON-POLYNOMIAL，把NP说成是NON-POLYNOMIAL，是望文生义，读书不求甚解。事实上，如果你能够证明某个 NP问题是个NON-POLYNOMIAL的问题，你就可以去领那七个百万美元数学大奖中间的一个了。数学上著名的NP问题，完整的叫法是NP完全问题，也即 “NP COMPLETE”问题，简单的写法，是 NP=P？的问题。问题就在这个问号上，到底是NP等于P，还是NP不等於P。证明其中之一，便可以拿百万美元大奖。这个奖还没有人拿到，也就是说，NP问题到底是Polynomial，还是Non-Polynomial，尚无定论。Mr. X信口开河敢说NP就是 Non-Polynomial，真是不知天高地厚，惹人笑话。 NP里面的N，不是Non-Polynomial的N，是Non-Deterministic， P代表Polynomial倒是对的。NP就是Non-deterministic Polynomial 的问题，也即是多项式复杂程度的非确定性问题。什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。前段时间轰动世界的一个数学成果，是几个印度人提出了一个新算法，可以在多项式时间内，证明某个数是或者不是质数，而在这之前，人们认为质数的证明，是个非多项式问题。可见，有些看来好像是非多项式的问题，其实是多项式问题，只是人们一时还不知道它的多项式解而已。

楼上说的什么啊看不懂啊就是做吗当然1个换1个了安全么是把

6，什么是PNPNPCNPhard问题

给你一个地址吧，那里介绍的很详细https://zhuanlan.zhihu.com/p/22497908

什么是np问题概念1:在计算机学科中，存在多项式时间的算法的一类问题，称之为p类问题；而像梵塔问题、推销员旅行问题、（命题表达式）可满足问题这类，至今没有找到多项式时间算法解的一类问题，称之为np类问题。概念2:多项式时间（polynomial time）在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。以数学描述的话，则可说m(n) = o(n)，此n为一常数值（依问题而定）拿推销员旅行问题为例，假设推销员亨利有向6个城市推销公司产品的任务，并规定了一个旅行预算。他手中有一张航班票价表，他要从a城开始走遍图中的6个城市后返回a城，并且不超出预算，请你帮他找出应走的路线。如果给出的预算宽裕，则任务很简单；如果预算比较紧张，你就得认真设计路线了。你得考虑每一种可能的次序，以使旅费最少。而np问题中最困难的问题称之为np完全问题(np-complete)，已经证明的包括：电话网络的最优几何设计、格子棋的最佳走法。根据库克定理，任意一个np完全问题如果能够在多项式时间内解决，则所有的np问题都能在多项式时间内解决，而至今这一问题仍无答案。什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间（多项式时间：运行时间最多是输入量的多项式函数）内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是著名的np=p？的猜想。解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定np完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。前段时间轰动世界的一个数学成果，是几个印度人提出了一个新算法，可以在多项式时间内，证明某个数是或者不是质数，而在这之前，人们认为质数的证明，是个非多项式问题。可见，有些看来好象是非多项式的问题，其实是多项式问题，只是人们一时还不知道它的多项式解而已。什么叫做np问题，什么叫做npc问题?首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。算法的复杂性是指解决问题的一个具体的算法的执行时间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度，是问题的性质。比如对于排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是o(nlgn)，但是排序算法有很多，冒泡法是o(n^2)，快速排序平均情况下是o(nlgn)等等，排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性问题，即提出一个问题，只需要回答yes或者no的问题。任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从a到b的最短路径，可以转化成：从a到b是否有长度为1的路径？从a到b是否有长度为2的路径？。。。从a到b是否有长度为k的路径？如果问到了k的时候回答了yes，则停止发问，我们可以说从a到b的最短路径就是k。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于p类问题。p类问题就是所有复杂度为多项式时间的问题的集合。然而有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为np问题。显然，所有的p类问题都是属于np问题的，但是现在的问题是，p是否等于np?这个问题至今还未解决。注意，np问题不一定都是难解的问题，比如简单的数组排序问题是p类问题，但是p属于np，所以也是np问题，你能说他很难解么？刚才说了，现在还不知道是否有p=np或者p<>np，但是后来人们发现还有一系列的特殊np问题，这类问题的特殊性质使得很多人相信p<>np，只不过现在还无法证明。这类特殊的np问题就是np完全问题（npc问题，c代表complete）。npc问题存在着一个令人惊讶的性质，即如果一个npc问题存在多项式时间的算法，则所有的np问题都可以在多项式时间内求解，即p=np成立！！这是因为，每一个npc问题可以在多项式时间内转化成任何一个np问题。比如前面说的哈米尔顿回路问题就是一个npc问题。npc问题的历史并不久，cook在1971年找到了第一个npc问题，此后人们又陆续发现很多npc问题，现在可能已经有3000多个了。所以，我们一般认为npc问题是难解的问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的np问题都存在多项式时间算法，这太不可思议了，但是也不是不可能）。类似哈米尔顿回路/路径问题，货郎担问题，集团问题，最小边覆盖问题（注意和路径覆盖的区别），等等很多问题都是npc问题，所以都是难解的问题。

文章TAG：p等于np 为什么p不等于np