当前位置：文档之家 › 深入浅出的讲解P与NP问题

深入浅出的讲解P与NP问题

  • 格式：pdf
  • 大小：129.12 KB
  • 文档页数：5

下载文档原格式

  / 5

合集下载

np问题 通俗解释

np问题 通俗解释

np问题通俗解释
NP问题是指“非确定性多项式时间”问题，也称为不可解问题。

它是计算机科学中的一个重要问题类别。

通俗来说，NP问题是指那些可以在多项式时间内验证是否解
答正确的问题，但尚未找到可以在多项式时间内解决的算法。

也就是说，虽然我们可以在多项式时间内检查一个给定解是否正确，但我们目前还没有找到一种高效的方法来找到一个解。

在计算理论中，NP问题是与P问题相对的一个概念。

P问题
是指可以在多项式时间内解决的问题。

一个经典的例子是旅行商问题。

在旅行商问题中，我们需要找到一条路径，使得旅行商可以经过多个城市，每个城市只到达一次，并且回到起点，同时总路径长度最短。

虽然我们可以在多项式时间内计算出给定路径的总长度，但当前还没有找到一种可以在多项式时间内找到最短路径的方法。

目前来说，还没有找到一种通用的解决NP问题的方法。

因此，研究人员一直在努力寻找解决这些问题的有效算法，或者找到一种方法来证明这些问题不存在多项式时间解决的算法。

P-NP-NPC三者问题阐述

P-NP-NPC三者问题阐述

P NP NPC三者问题阐述1）”P对NP问题”是什么意思？首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。

算法的复杂性是指解决问题的一个具体的算法的执行时间,这是算法的性质；问题的复杂性是指这个问题本身的复杂程度，是问题的性质.比如对于排序问题,如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息,则排序问题的复杂性是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?这个问题至今还未解决。

P与NP问题之我见

P与NP问题之我见

P与NP问题之我见孤维摘要：不一的两者之间能否相等，取决于它们被强调相等内容之间的一致性程度。

关键词：无关，相关，相异，同一，相等。

一.关于可解与可计算人们在实践中遇到的问题，总是伴随着他们对客体世界认识的深入而增多。

为了解决这些问题，免不了要处理许多数据。

当这些数据的量大到所谓天文数字时，对人们自己使用的工具——计算机的运算速度便提出了苛刻的要求——要多快，运算速度就有多快。

然而对于自身是有限的一台计算机来说，它不可能无限的快。

因为我们永远没有．．。

．．无限．．能力在有限．．内．，容下或将有限．．．。

．．本身．．无限化由此及彼，计算机运算的速度再快，处理数据的单位时间能力始终存在一个极限。

所以必须得到充裕时间的支持。

如：求一个推销员行走20 座城市的最短路径问题的解，即便每秒排100 万次，计算机也需要三千余年的时间才能完成。

[1]这实际上已没有什么现实意义。

而且它还远未涉及这台计算机能否连续运行三千余年这个不可回避的实际问题。

这便是人们所说的呈指数性上升的时间算法是计算机面临的最大难题。

很显然，这个问题不是计算机本身能解决的。

只能责无旁贷的由它的创造者——人来承担。

显而易见，一般来说问题的“可解性”涉及如下两个方面：一，问题本身是否存在解。

二，是否有相应可解的算法。

如果以上两个都不存在问题，则求解的过程，即对算法的执行——也就是计算便至关紧要。

就目前计算机所遇到的困难而言：在某种程度上仍取决于．．．．．．需解问题的规模．．决定的计算量与计算机运算速度．．。

．．．．之间的比值．．关系也就是：运算速度．．．．一定，计算量越．多．，所需时间越．长．。

计算量．．，所需时间也越短．．。

．．．一定，运算速度越快虽然从原则上来说：问题的规模．．．的。

．．．．．凡是可．穷．的都是可．解．的，亦是可计算但实际上我们无法对“可穷”进行量的界定。

如推销员行走的最短路径问题。

即使城市的数量k为可穷尽的20座都需计算3000余年，才能求出解。

什么是P问题、NP问题和NPC问题PPT课件

什么是P问题、NP问题和NPC问题PPT课件
不管数据有多大，程序处理花的时间始终是那么多的，我们 就说这个程序很好，具有O(1)的时间复杂度，也称常数级复 杂度；
2020/10/13
2
先用几句话简单说明一下时间复杂度
数据规模变得有多大，花的时间也跟着变得有多长， 这个程序的时间复杂度就是O(n)，比如找n个数中 的最大值；
而像冒泡排序、插入排序等，数据扩大2倍，时间 变慢4倍的，属于O(n^2)的复杂度。
因此，我们会说，一个O(0.01*n^3)的程序的效率 比O(100*n^2)的效率低，尽管在n很小的时候，前 者优于后者，但后者时间随数据规模增长得慢，最 终O(n^3)的复杂度将远远超过O(n^2)。我们也说， O(n^100)的复杂度小于O(1.01^n)的复杂度。
2020/10/13
4
先用几句话简单说明一下时间复杂度
2020/10/13
8
NP问题
我说，我RP很好，肯定能随便给你指条很短的路出来。然后 我就胡乱画了几条线，说就这条吧。那人按我指的这条把权 值加起来一看，嘿，神了，路径长度98，比100小。于是答 案出来了，存在比100小的路径。
别人会问他这题怎么做出来的，他就可以说，因为我找到了 一个比100 小的解。
2020/10/13
5
不可解问题
自然地，人们会想到一个问题：会不会所有的问题都 可以找到复杂度为多项式级的算法呢？
答案是否定的。有些问题甚至根本不可能找到一个正 确的算法来，这称之为“不可解问 题”(Undecidable Decision Problem)。
例如：
Hamilton回路。
问题是这样的：给你一个图，问你能否找到一条经过每个顶 点一次且恰好一次（不遗漏也不重复）最后又走回来的路 （满足这个条件的路径叫做Hamilton回路）。

什么是P问题、NP问题和NPC问题PPT课件

什么是P问题、NP问题和NPC问题PPT课件
解的问题。NP问题的另一个定义是，可以在 多项式的时间里猜出一个解的问题。
比方说，我RP很好，在程序中需要枚举时，我可 以一猜一个准。
现在某人拿到了一个求最短路径的问题，问从起点 到终点是否有一条小于100个单位长度的路线。它 根据数据画好了图，但怎么也算不出来，于是来问 我：你看怎么选条路走得最少？
2020/10/13
12
NPC问题
人们如此坚信P≠NP是有原因的，就是在研究 NP问题的过程中找出了一类非常特殊的NP问 题叫做NP-完全问题，也即所谓的 NPC问题。 C是英文单词“完全”的第一个字母。正是 NPC问题的存在，使人们相信P≠NP。
2020/10/13
8
NP问题
我说，我RP很好，肯定能随便给你指条很短的路出来。然后 我就胡乱画了几条线，说就这条吧。那人按我指的这条把权 值加起来一看，嘿，神了，路径长度98，比100小。于是答 案出来了，存在比100小的路径。
别人会问他这题怎么做出来的，他就可以说，因为我找到了 一个比100 小的解。
因此，我们会说，一个O(0.01*n^3)的程序的效率 比O(100*n^2)的效率低，尽管在n很小的时候，前 者优于后者，但后者时间随数据规模增长得慢，最 终O(n^3)的复杂度将远远超过O(n^2)。我们也说， O(n^100)的复杂度小于O(1.01^n)的复杂度。
2020/10/13
4
先用几句话简单说明一下时间复杂度
2020/10/13
10
NP问题
之所以要定义NP问题，是因为通常只有NP问 题才可能找到多项式的算法。
我们不会指望一个连多项式地验证一个解都不 行的问题存在一个解决它的多项式级的算法。
很显然，所有的P类问题都是NP问题。也就是 说，能多项式地解决一个问题，必然能多项式 地验证一个问题的解——既然正解都出来了， 验证任意给定的解也只需要比较一下就可以了。

离散数学P和NP类问题比较

离散数学P和NP类问题比较

离散数学P和NP类问题比较离散数学中的P类和NP类问题是计算机科学中非常重要的概念。

它们帮助我们确定问题的复杂性，并为算法设计和问题求解提供了基础。

本文将比较P类和NP类问题的特点和区别。

一、P类问题P类问题是可以在多项式时间内解决的问题。

也就是说，存在一种算法可以在输入规模的多项式函数内，有效地计算出问题的解。

例如，排序、求和等基本算法属于P类问题。

P类问题具有以下特点：1. 可以在多项式时间内解决。

2. 可以使用确定性算法或非确定性算法进行求解。

3. 可以验证问题的解的正确性。

二、NP类问题NP类问题是可以在多项式时间内验证解的问题。

虽然无法在多项式时间内求解，但可以在多项式时间内验证给定解是否为问题的解。

例如，旅行商问题和背包问题就属于NP类问题。

NP类问题具有以下特点：1. 无法在多项式时间内求解。

2. 可以使用非确定性算法验证解的正确性。

3. 如果一个P类问题可以在多项式时间内约化为NP类问题，那么该P类问题就属于NP类问题。

三、P类和NP类问题的关系P类和NP类问题之间存在许多关系和区别。

1. P类问题是NP类问题的一个子集。

也就是说，所有的P类问题都属于NP类问题。

2. P类问题可以在多项式时间内求解，而NP类问题只能在多项式时间内验证解的正确性。

3. 目前还无法确定P类问题是否等于NP类问题。

这是著名的P与NP问题，其解决将对计算机科学有极其重要的影响。

4. 如果某个NP类问题可以在多项式时间内求解，那么它将成为P 类问题。

这样的问题被称为NP完全问题。

四、NP完全问题NP完全问题是NP类问题中最困难的一类问题。

如果一个NP问题可以在多项式时间内约化为一个已知的NP完全问题，那么该问题本身也属于NP完全问题。

著名的NP完全问题包括旅行商问题、图着色问题和集合覆盖问题等。

NP完全问题具有以下特点：1. 它是NP类问题中最困难的问题。

2. 尚未找到多项式时间内求解NP完全问题的算法，因此被认为无法在多项式时间内求解。

P和NP问题详解

时间复杂度：时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。

不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，则这个程序的时间复杂度就是O(n)。

多项式级的复杂度：如O(1)，O(log(n))，O(n^a)等——注意它的规模n出现在底数的位置！非多项式级的复杂度：如：O(a^n)和O(n!)等。

P/NP问题：P问题即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；NP问题由所有可以在多项式时间内验证解是否正确的决定问题组成，或者等效的说，那些解可以在非确定型图灵机上在多项式时间内找出的问题的集合。

简单地说，P问题是指可以在多项式复杂度的时间内解决的问题，NP是可以在多项式复杂度的时间内验证解是否是正确的问题。

P属于NP。

NP=Non-deterministic Polynomial。

Example：当你计算两个数字的和时，这类问题很快就经过一系列有限的基本步骤而解出来了，这就是一个P问题；另一类问题计算过程比较繁琐，但验证答案却很容易，比如把整数44427进行因数分解，求解过程可能会很费时，但如果告诉你答案是177×251，简单计算即可验证答案是对的，这类问题（分解因子）就被归为NP问题。

NP问题有很多，例如著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，…，等n 个城市，最后返回香港。

任意两个城市之间都有飞机直达，但票价不等。

现在假设公司只给报销C 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于C？推销员旅行问题显然是NP 的。

因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。

但是，要想知道一条总路费小于C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排！但n很大时，这将是个天文数字。

算法设计与分析课件--NP完全性理论-P类和NP类问题

➢ 若用邻接矩阵C表示图G，使用二进制串表示C和k，则
团问题的一个实例可以用长度为n2 + log k + 1 的二
进位串表示。
➢ 无向图的团问题可表示为语言：
• CLIQUE = {w#v|w,v∈{0,1}*，以w为邻接矩阵的图G有一个k 顶点的团。其中，w是C的二进制表示，v是k的二进制表示。}
• STEP3：确定性地检查V’的团性质。若V’是一个团则接受输入，
否则拒绝输入。时间复杂度为O(n 4 ) 。 • 因此，整个算法的时间复杂性为：O(n 4 ) 。
❖非确定性算法在多项式时间内接受语言CLIQUE，故CLIQUE∈NP。
16
8.2 P类问题和NP类问题
◼ P类问题和NP类问题的关系：
算法设计与分析
1
第八章 NP完全性理论
目录
8.1 易解问题和难解问题
8.2 P类问题和NP类问题
8.3
NP完全问题
8.4 NP完全问题的近似算法
2
8.1 易解问题和难解问题
◼ 常见的几类算法复杂性：
➢ O(1)：常数阶； ➢ O(log2n), O(nlog2n)：对数阶； ➢ O(n), O(n2), O(n3), …, O(nk): 多项式阶。多项式时间算法； ➢ O(2n), O(n!), O(nn)：指数阶。指数时间算法。
12
8.2 P类问题和NP类问题
◼ NP(Non-deterministic Polynomial)类问题：
➢ 如对于某个判定问题，存在一个非负整数k，对于输入规模为n的实 例，能以O(nk)的时间运行一个非确定性算法得到是或否的答案。 • 能用非确定算法在多项式时间内求解的判定问题。如哈密尔顿回 路问题。 • NP类问题是难解问题的一个子类。 • NP类问题并不要求给出一个算法来求解问题本身，而只要求给 出一个确定性算法在多项式时间验证它。

P问题、NP难问题详解


NPC问题（补充） 问题（补充） 问题
NPC问题存在吗 问题存在吗? 问题存在吗
•？
NPC问题（补充） 问题（补充） 问题
• 逻辑电路问题 给定一个逻辑电路，问是否存在一种输入 逻辑电路问题: 给定一个逻辑电路， 使输出为True。 使输出为 。 • 这是第一个 这是第一个NPC问题。其它的 问题。 问题 其它的NPC问题都是由这个问题约 问题都是由这个问题约 化而来的。因此，逻辑电路问题是NPC类问题的“鼻祖”。 类问题的“ 化而来的。因此，逻辑电路问题是 类问题的 鼻祖” • 我们知道，一个逻辑电路由若干个输入，一个输出，若干 我们知道，一个逻辑电路由若干个输入，一个输出， 逻辑门”和密密麻麻的线组成，如下图： “逻辑门”和密密麻麻的线组成，如下图： •
浅谈P问题、NP问题、 NPC问题及NP难问题
王培磊
Contents
1 2 3 4
P问题 问题
NP问题、 问题、 问题
NPC问题 问题
NP难问题 难问题
时间复杂度
• 时间复杂度并不是表示一个程序解决问题需要花多少时间， 而是当问题规模扩大后，程序需要的时间长度增长得有多 快。 • 不管数据有多大，程序处理花的时间始终是那么多的，我 们就说这个程序很好，具有O(1)的时间复杂度，也称常数 级复杂度；数据规模变得有多大，花的时间也跟着变得有 多长，这个程序的时间复杂度就是O(n)。
NPC问题（补充） 问题（补充） 问题
• 有输出无论如何都不可能为 有输出无论如何都不可能为True的逻辑电路吗？ 的逻辑电路吗？ 的逻辑电路吗
NPC问题（补充） 问题（补充） 问题
其大概意思是说任意一个NP问题的 其大概意思是说任意一个 问题的 输入和输出都可以转换成逻辑电路 的输入和输出（ 的输入和输出（想想计算机内部也 的运算）， 不过是一些 0和1的运算），因此对 和 的运算），因此对 于一个NP问题来说 问题来说， 于一个 问题来说，问题转化为了 求出满足结果为True的一个 求出满足结果为 的一个 输 即一个可行解）。 入（即一个可行解）。 • 逻辑电路问题属于NPC问题——它显然属于NP问题，并且 可以证明所有的NP问题都可以约化到它 。

P问题、NP问题、NP完全问题和NP难问题

P问题、NP问题、NP完全问题和NP难问题在讲P类问题之前先介绍两个个概念：多项式，时间复杂度。

(知道这两概念的可以⾃动跳过这部分)1、多项式：axn-bxn-1+c恩....就是长这个样⼦的，叫x最⾼次为n的多项式....咳咳，别嫌我啰嗦。

有些⼈说不定还真忘了啥是多项式了。

例如第⼀次看到的鄙⼈→_→2、时间复杂度我们知道在计算机算法求解问题当中，经常⽤时间复杂度和空间复杂度来表⽰⼀个算法的运⾏效率。

空间复杂度表⽰⼀个算法在计算过程当中要占⽤的内存空间⼤⼩，这⾥暂不讨论。

时间复杂度则表⽰这个算法运⾏得到想要的解所需的计算⼯作量，他探讨的是当输⼊值接近⽆穷时，算法所需⼯作量的变化快慢程度。

举个例⼦：冒泡排序。

在计算机当中，排序问题是最基础的，将输⼊按照⼤⼩或其他规则排好序，有利于后期运⽤数据进⾏其他运算。

冒泡排序就是其中的⼀种排序算法。

假设⼿上现在有n个⽆序的数，利⽤冒泡排序对其进⾏排序，①⾸先⽐较第1个数和第2个数，如果后者>前者，就对调他们的位置，否则不变②接着⽐较第2个数和第3个数，如果后者>前者，就对调他们的位置，否则不变③⼀直向下⽐较直到第n-1和第n个数⽐较完，第⼀轮结束。

（这时候最⼤的数移动到了第n个数的位置）④重复前三步，但是只⽐较到第n-1个数（将第⼆⼤的数移动到第n-1个数位置）⑤持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较。

举个实例：5,4,3,2,1，对其进⾏排序，先是⽐较5跟4变成4,5,3,2,1，第⼀轮结束后变成43215，可以计算，当对其排序完正好要经过4+3+2+1=10次⽐较，当然这是最复杂的情况，即完全反序。

可以知道对于n个数，⾄多要经过1+2+...+n-1即(n^2-n)/2次⽐较才能排好序。

这个式⼦⾥n的最⾼次阶是2，可知道当n→∞时，⼀次性对其⽐较次数影响很⼩，所以我们把这个算法的时间复杂度⽐作：o(n^2)。

取其最⾼次，可以看出，这是⼀个时间复杂度为多项式的表⽰⽅式。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

可能的极为诡异的结果 从实际应用来说，人们都希望NP=P，因为这意味着很多问题都能有有效的算法，但有些极为诡 异的结果也是可能的，人们从这个结果中什么都得不到。
比如某一天人们最终使用某种数学上的技巧证明了NP问题的多项式时间算法的存在性，但并不 知道如何找到它——这在数学上是极为可能的，那最终会怎么样呢？
一个问题的规模指的是输入的总位数，比如一个n个数的排序问题，输入规模就是n。注意，在 某些时候，输入规模是要值得注意的，比如判定一个数n是否是一个质数这个问题，它的输入规 模并不是n，而是log(n)，因为一个数n用大约log(n)位就能表示出来了，这也是为何枚举因子 判定素数的算法并不是多项式时间P完全问题。
当然，这种问题具体是什么样子，是无法用直观的语言表示出来，它纯粹是一个数学上的构造 性证明。
参阅：
Complexity classes P and NP - Wikipedia, the free encyclopedia, P/NP问题- Wikipedia Turing machine - Wikipedia, the free encyclopedia, 图灵机- Wikipedia NP-hard - Wikipedia, the free encyclopedia,
1. P=NP will be resolved between 2002-2009: 5 2. P=NP will be resolved between 2010-2019: 12 3. P=NP will be resolved between 2020-2029: 13 4. P=NP will be resolved between 2030-2039: 10 5. P=NP will be resolved between 2040-2049: 5 6. P=NP will be resolved between 2050-2059: 12 7. P=NP will be resolved between 2060-2069: 4 8. P=NP will be resolved between 2070-2079: 0 9. P=NP will be resolved between 2080-2089: 1 10. P=NP will be resolved between 2090-2099: 0 11. P=NP will be resolved between 2100-2110: 7 12. P=NP will be resolved between 2100-2199: 0 13. P=NP will be resolved between 2200-3000: 5 14. P=NP will never be resolved : 5.
FOR N = 1…infinity FOR P = 1…N 以S为输入运行程序数P N步 IF 程序输出一个完整的数学证明 AND 证明的每一步合法 AND 结论是S确实有（或者没有）一个和为0的子集 THEN OUTPUT 是（或者不是）并停机
如果NP=P，上面这个算法便是一个NP完全问题的多项式时间算法。可是它一点价值都没有，更 不用说来解决实际问题了。
姚期智: (Princeton) It's hard to say when the question will be resolved. I don't have even an educated guess. Probably the resolution is that P is not equal to NP. I think the mathematical techniques used will be beautiful.
如果一个算法，它能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多项式 时间算法。注意：这里的多项式时间是指算法运行的步数。一个算法是否是多项式算法，与计 算模型的具体的物理实现没有关系，虽然大多数假想的计算模型不可能有任何物理的实现。
P指确定型图灵机上的具有多项式算法的问题集合，NP指非确定型图灵机上具有多项式算法的问 题集合，这里N是Non-Deterministic的意思（图灵机的概念见理论计算机初步：算法和计算模 型）。
问题的解决。
而几乎所有NP里面无法确定是否属于P的问题最后都被证明为NP完全。正因为如此，多数理论计 算机学家都猜测P≠NP。目前已知的NP完全问题数以千计，上面引用中的例子都是完全问题，更 多NP完全问题见NP完全问题的不完全列表。
一个很自然的想法是如果NP≠P，则NP-P里面的问题都是完全问题。至少有两个自然的问题，一 个是大数分解（给出一个数的质因数分解式），另一个是图同构问题（给出两个图，它们是否 同构），它们既没有被证明是P的，也没有被证明是NP-完全。但是更惊人的是还有这个定理：
人们为何要提出NP问题？因为，大多数遇到的自然的难解问题，最后都发现它们是NP问题。如 果我们能证明NP跟P的关系，则解决了无数问题的算法复杂度问题。
NP里面有无数个不同的问题，我们是否要一个一个地判定它们是否属于P呢？P vs NP问题的美 妙和简洁之处便在于在NP中，有一个子类，NP完全(NP Complete，简记为NPC)问题，指的是那 些NP中最难的那些问题：所有其它的NP问题都可以归约到这些NP完全问题。也就是说，只要这 些NP完全问题的某一个得到解决，无论是证明其存在多项式算法，还是不存在，都意味着P vs NP
这种情况不会发生，事实上，在NP=P的假设下，人们已经找到了NP完全问题的多项法解法，但 这并没有好太多，因为这个算法是这样的：
// 接受NP完全语言的一个算法。 // // 这是一个多项式时间算法当且仅当P=NP。 // // “多项式时间”表示它在多项式时间内返回“是”，若 // 结果是“是”，否则永远运行。 // // 输入：S = 一个自然数的有限集 // 输出：是 如果某个S的子集加起来等于0。 // 否则，它永远运行没有输出。 // 注：上面这是一个NP完全问题 // // 程序数P 是你将一个整数P写为二进制，然后 // 将位串考虑为一个程序。 // 每个可能的程序都可以这样产生， // 虽然多数什么也不做因为有语法错误。
证明技巧。
但是，明显的，目前还没有一个看上去有希望的方向。相反的，1993年Razborov和Rudich证明 的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P vs NP问 题。这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定 理的可能证明有越来越多的陷阱要规避。
脱离图灵机的概念，就在普通的计算机上看，P问题是指能够在多项式时间求解的判定问题（判 定问题指只需要回答是和不是的问题），而NP问题则是指那些其肯定解能够在给定正确信息下 在多项式时间内验证的判定问题。比如，要判定一个数是合数，如果给我一个约数，我们就很 快判定它就是合数。所以判定一个数是合数的问题属于NP。 下面是一些NP问题的例子：
数学里最伟大的定理之一——费马大定理，用了数学家300多年时光。P vs NP问题，作为理论 计算机领域最困难的问题，40年时间似乎太短了。
不过我还是相信，这个问题被拖这么长时间，是因为没有足够伟大的数学家来做这个问题。
大牛们怎么看？ 对于NP是否等于P，大家看法不一。在2002年对于100个研究者的调查中，61人相信答案是否定 的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所 以不可能证明或证否。同时，在被询问到这个问题可能在何时被解决时，79个人给出了确切的 数字，统计结果如下：
The only thing I can definitely say, is that it is one of the most important and interesting questions ever asked by humans, and more people and resources should participate in filling up the holes that would allow better guesses of answers to your questions.
零子集和问题 给n个整数，判断是否可以从中找到若干个数，其和为0。
旅行商问题 有n个城市，一个推销员要从其中某一个城市出发，不重复地走遍所有的城市，再回到他出发的 城市。问这个推销员的最短路程(是否小于指定的K)。
从上面的定义知道，NP包含P。P vs NP问题指P是否完全等于NP，即确定型图灵机和非确定图灵 机的性能是否一样。
另一种可能性：独立问题？ 自从Godel的开创性结果以来，我们知道某些问题，比如连续统假设，是不可能从目前的条件（公 理系统）推导出来的。有人怀疑P vs NP问题也是这样。这样的话，如果不存在NP完全问题的有 效算法，我们不可能证明这一点。同样，如果存在一个有效的算法，我们也不可能找到它。
在这份调查报告中，还有国际上著名的计算机学家对这个问题的看法，比如：
Avi Wigderson: (Institute of Advanced Study) I think this project is a bit premature. I think we know too little of what is relevant to even guess answers to your questions, certainly if "we" s replaced by "I"
理论计算机初步：P vs NP - 历史，现状和未来 ©Zhang-Zi, August 24, 2006
上篇文章已经提到，P vs NP是理论计算机科学的核心问题。从数学的角度来说，它和其他历史 上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有 关的的学术领域中，NP-完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独 立的智力游戏，而是对计算机科学有全面影响力的问题。