下载文档原格式
P、NP、NPC、NPH问题的区别和联系P问题 如果⼀个问题能找到在多项式时间内解决它的算法，那么我们说该问题是P类问题。
P是多项式（Polynomial）的第⼀个字母。
⽐如排序问题就是⼀个P问题，因为我们可以找到⼀个时间复杂度为O(n2)O(n2)的冒泡排序算法。
NP问题 ⼀些问题我们很难在多项式时间内找到解决问题的算法，但是如果别⼈给了我⼀个解，我可以很快地验证该解是不是问题的正确答案。
⽐如在汉密尔顿回路问题中，我想验证⼀条路径是否正确，则验证路径是否正确的时间复杂度为O(n)O(n)，为多项式级的时间复杂度。
也就是说直接找NP问题的⼀个解可能很慢，当验证NP问题的解却很快。
NPC问题 所有P问题都是NP问题，因为能在多项式时间内解决的问题也能够在多项式时间内验证解的正确性。
是否所有的NP问题都是P问题，这就是著名的“P对NP问题（P=NP?）”。
在2000年美国的Clay数学研究所公布的七个千年数学难题中，P对NP问题位居榜⾸，可见解决该问题的难度。
由于直接证明P对NP问题过于复杂，⼈们引⼊了另⼀类问题--NPC问题（NP -complete，NP-完全问题）。
规约 假设有两个问题A和B，对问题A的输⼊a经过某种规则转换为对问题B的输⼊b，⽽A(a)和B(b)的结果相同，也就是说我们可以将求解A 问题转换为求解B问题，或者说可以⽤解决问题B的⽅法解决问题A，那我们称A可以归约（reducibility，或“约化”）到B。
超级NP问题 是否可以将若⼲相对不那么复杂NP问题不断归约，从⽽得到⼀个最难的“超级NP问题”，所有的NP问题都可以归约到这个“超级NP问题”，只要解决了这个“超级NP问题”，那么也就意味着所有NP问题都可以被解决。
事实上，存在这样的⼀类“超级NP问题”，这也就是我们所说的NPC问题。
NPC问题的定义如下：如果⼀个问题Q，它满⾜以下两条性质：(1). Q是NP问题(2). 任⼀NP问题都可在多项式时间内归约到问题Q那么我们说问题Q是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/NPC 问题及密码学中的主流困难性问题一、图灵机图灵机（英语：Turing machine ），又称确定型图灵机，是英国数学家阿兰·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：（a ）在纸上写上或擦除某个符号；（b ）把注意力从纸的一个位置移动到另一个位置。
而在每个阶段，人要决定下一步的动作，依赖于：（a ）此人当前所关注的纸上某位置的符号和（b ）此人当前思维的状态。
为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：一条无限长的纸带TAPE ；一个读写头HEAD ，可以在纸带上左右移动并能读出和改变当前所指的格子上的符号；一套控制规则TABLE ，根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入新的状态。
一个状态寄存器。
它用来保存图灵机当前所处的状态。
图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。
图灵机的标准定义如下：一台图灵机是一个七元组0(,,,,,,)accept reject Q q q q δ∑Γ，其中,,Q ∑Γ都是有限集合，且满足Q 是状态集合；∑是输入字母表，其中不包含特殊的空白符；b ∈Γ为空白符；Γ是带字母表，其中∈Γ且∑∈Γ；:{,}Q Q L R δ⨯Γ→⨯Γ⨯是转移函数，其中,L R 表示读写头是左移还是右移； 0q Q ∈是起始状态；accept q Q ∈是接受状态；reject q Q ∈是拒绝状态，且accept reject q q ≠。
图灵机0(,,,,,,)accept reject M Q q q q δ=∑Γ将以如下方式运作：开始的时候将输入符号串*011n ωωωω-=∈∑从左到右依此填在纸带的第0,1,,1n -号格子上，其他格子保持空白（即填以空白符）。
P问题、NP问题、NPC问题、NP难问题的概念2010-04-15 21:35 | (分类:默认分类)转自/view/3e968900a6c30c2259019e8f.html你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。
你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。
他们没有搞清楚NP问题和NPC问题的概念。
NP问题并不是那种“只有搜才行”的问题，NPC问题才是。
好，行了，基本上这个误解已经被澄清了。
下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。
接下来你可以看到，把NP问题当成是NPC问题是一个多大的错误。
还是先用几句话简单说明一下时间复杂度。
时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。
也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。
不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。
还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。
不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。
同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。
因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。
P/NP问题P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”（Clay Mathematics Institute, 简称CMI）在千禧年大奖难题中收录。
P/NP问题中包含了复杂度类P与NP的关系。
1971年史提芬·古克(Stephen A. Cook) 和Leonid Levin 相对独立的提出了下面的问题,即是否两个复杂度类P和NP是恒等的（P=NP?）。
P和NP复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。
很可能，计算理论最大的未解决问题就是关于这两类的关系的:P和NP相等吗?在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。
[1] 对于正确的解答，有一个,000,000美元的奖励。
NP-完全问题(或者叫NPC)的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在NP中最不像在P中的。
(确切定义细节请参看NP-完全)理论计算机科学家现在相信P, NP,和NPC类之间的关系如图中所示，其中P和NPC类不交。
假设P ≠ NP的复杂度类的图解.如P = NP则三个类相同.本质上，P = NP问题问道：如果是/不是问题的正面答案可以很快验证，其答案是否也可以很快计算？这里有一个给你找点这个问题的感觉的例子。
给定一个大数Y,我们可以问Y是否是复合数。
例如，我们可能问53308290611是否有非平凡的因子。
回答是肯定的，虽然手工找出一个因子很麻烦。
从另一个方面讲，如果有人声称答案是"对，因为224737可以整除53308290611",则我们可以很快用一个除法来验证。
P、NP、NP-hard、NPC问题P问题：⼀个问题可以在多项式的时间得到解决。
P为英⽂polynominal的⾸字母。
多项式时间的时间复杂度例如O(n)、O(n^2)等等。
NP问题：NP问题可能没有⼀个已知的快速解决⽅案。
但如果能够在多项式的时间内验证⼀个解是否正确，则称此问题为NP问题。
例如根据数据画好了⼀个图。
求解能否找到权重和⼩于100的⽣成树。
这个问题可以在多项式的时间内得到验证。
假设你运⽓好，随⼿⼀画就得到了⼩于100的⽣成树，验证的⽅法只需要将⽣成树的所有树边权重相加。
时间复杂度为O(V)。
V代表树的结点树，⽣成树的边数为|V|-1。
提到NPC问题之前需要了解的概念是规约。
例如⼀个问题A可以约化为问题B的含义是，可以⽤问题B的解法来解决问题A。
或者说A可以转化为B。
例如求⼀元⼀次⽅程可以规约到求⼀元⼆次⽅程。
将⼀元⼆次⽅程的⼆次项系数变为0。
这样两个问题就等价了。
通过实例也可看出问题B不⽐问题A简单，即问题B的时间复杂度⾼于或者等于A。
规约是具有传递性的。
A规约成B，B规约成C，则A能够规约成C。
通过不断地规约，我们能得到复杂度更⾼但是应⽤范围更⼴的算法来代替复杂度虽低但是应⽤范围⼩的⼀类问题的算法。
根据传递性，最终可以得到⼀个复杂度最⾼，并且可以解决所有NP问题的NP问题。
这就是NPC问题，即NP完全问题。
NPC不⽌⼀个，⽽是⼀系列问题。
证明⼀个问题是NPC问题的步骤：1.⾸先要证明此问题是⼀个NP问题。
2.证明⼀个已知的NPC问题能够规约到此问题。
已知的NPC问题，给定⼀个逻辑电路，是否存在⼀种输⼊使得输出为True。
所有的NP问题都可以规约到逻辑电路问题。
直观地解释是计算机中所有的程序最终都转化成01组成的机器语⾔执⾏。
另外⼀个⽐较神奇的问题是，因为NPC问题是NP问题不断规约⽽来的，所以如果能证明⼀个NPC问题可以在多项式时间内解决。
那么所有的NP问题都能在多项式时间内解决。
什么是P、NP、NPC、NP优化问题在磕盐的时候经常会遇到，其中经常涉及到某某问题是NP的之类的论断，因此花了一点时间整理了一下NP问题的相关知识，在研究过程中看到一篇很好的文章，因此下面的整理主要基于这篇文章《什么是P问题、NP问题和NPC问题》，有兴趣的同学可以仔细阅读原文，时间紧张的话可以直接看下面我整理的内容。
author: @Huji预备知识时间复杂度表明问题规模扩大后，程序需要的时间长度增长得有多快。
程序的时间复杂度一般可以分为两种级别：- 多项式级的复杂度，如O(1)，O(log(n))、O（n^a）等，- 非多项式级的，如O(a^n)、O(n!)等。
后者的复杂度计算机往往不能承受。
约化(Reducibility)简单的说，一个问题A可以约化为问题B的含义是，可以用问题B的解法解决问题A。
（个人感觉也就是说，问题A是B的一种特殊情况。
）标准化的定义是，如果能找到一个变化法则，对任意一个A 程序的输入，都能按照这个法则变换成B程序的输入，使两程序的输出相同，那么我们说，问题A可以约化为问题B。
例如求解一元一次方程这个问题可以约化为求解一元二次方程，即可以令对应项系数不变，二次项的系数为0，将A的问题的输入参数带入到B问题的求解程序去求解。
另外，约化还具有传递性，A可以化约为B，B可以约化为C，那么A也可以约化为C。
基本概念•P Problem: 对于任意的输入规模n，问题都可以在n的多项式时间内得到解决；•NP(Non-deterministic Polynomial)Problem: 可以在多项式的时间里验证一个解的问题；•NPC(Non-deterministic PolynomialComplete) Problem: 满足两个条件 (1)是一个NP问题(2)所有的NP问题都可以约化到它•NP-Hard Problem: 满足NPC问题的第二条，但不一定要满足第一条详解P Problem如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题，即算法的时间复杂度是多项式级的。
P、NP、NPC、NP-Hard问题到底是何⽅神圣？最近在做⼀个求解有向图中回路的问题，⽼师说求解图中全部回路是⼀个NP难问题。
突然想到P、NP、NPC、NP-hard的描述⼀致不是很清楚，所以⼜学习了⼀下。
在解释这四个概念之前，我们需要先知道两个问题多项式时间和规约，我们⾸先来看多项式时间，⼀个算法可以在多项式时间内解决即指⼀个算法的时间复杂度是为多项式——ax n+bx n−1+⋯+x+c，例如o(1)、o(lnn)、o(n a)等，我们成为多项式级复杂度，⽽o(a n)这类指数级复杂度我们称之为⾮多项式级复杂度。
再看规约，问题A可以约化为问题B，称为“问题A可规约为问题B”，可以理解为问题B的解⼀定就是问题A的解，因此解决A不会难于解决B。
由此可知问题B的时间复杂度⼀定⼤于等于问题A。
《算法导论》中有⼀个例⼦，现在有两个问题：求解⼀个⼀元⼀次⽅程和求解⼀个⼀元⼆次⽅程。
那么我们说，前者可以规约为后者，意即知道如何解⼀个⼀元⼆次⽅程那么⼀定能解出⼀元⼀次⽅程。
我们可以写出两个程序分别对应两个问题，那么我们能找到⼀个“规则”，按照这个规则把解⼀元⼀次⽅程程序的输⼊数据变⼀下，⽤在解⼀元⼆次⽅程的程序上，两个程序总能得到⼀样的结果。
这个规则即是：两个⽅程的对应项系数不变，⼀元⼆次⽅程的⼆次项系数为0。
P类问题(Polynomial)P类问题，由其名字（Polynomial）我们不难看出它指的就是能在多项式时间内解决的问题，亦即解决这个问题的算法的时间复杂度是是多项式。
NP问题(Non-deterministic Polynomial)在多项式时间内可判定其答案是否正确的问题。
也就是说，不能判定这个问题是否能在多项式时间内求得其解，但是对于这个问题的⼀个解可以在多项式时间内证明是否正确的。
即该问题的求解过程是不确定的，⽽对其某⼀个解的验证则能够在多项式时间内完成。
因⽽显然P类问题是NP问题的⼦集，因为倘若⼀个问题可以在多项式时间内被求解，那么这个解也⼀定可以在多项式时间内被验证是否正确。
转载：澄清P问题、NP问题、NPC问题的概念你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。
你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。
他们没有搞清楚NP问题和NPC问题的概念。
NP问题并不是那种“只有搜才行”的问题，NPC问题才是。
好，行了，基本上这个误解已经被澄清了。
下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。
接下来你可以看到，把NP问题当成是NPC问题是一个多大的错误。
还是先用几句话简单说明一下时间复杂度。
时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。
也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。
不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。
还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。
不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。
同样地，O(n^3+n^2)的复杂度也就是O(n^3)的复杂度。
因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。
我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。
