npc是什么意思

NP问题总结（概念+例⼦+证明）

⽬录

基本概念

P类问题:(polynominal)存在多项式时间算法的问题，即在多项式时间内可解的问题；

例如：冒泡排序、快速排序等问题；

NP类问题:(Nondeterministicpolynominal)能在多项式时间内验证出⼀个正确解的问题，也就是说这个问题不⼀定在多项式时间内可

解，但可以在多项式时间内验证；

例如：⼤数分解问题，⽐如180576这个数让你拆成两个数相乘，必须是三位乘以三位的，可能很久都解不出来（如果是⼀个很⼤很⼤的

数的话），但是我告诉你这是352*513得到的，那么很简单就能在多项式时间内验证是否正确，这就是NP问题；

NPC类问题（NondeterminismPolynomialcomplete）：存在这样⼀个NP问题，所有的NP问题都可以约化成它。

NP-Hard类问题（NondeterminismPolynomialhard）：所有的NP问题都可以约化成它。

这⾥插⼀句，何为约化，以及两者的具体解释我在下⾯给出，但是可以看的所谓的NP完全问题和NP难问题的唯⼀差别就是这个问题本⾝是

不是NP问题。然后两者都是可以被所有NP问题约化的。那也就是说，NP-H问题是包含NPC问题的，⽽NPC⼜⾄少是⼀个NP问题，那么

它也被NP包含，但NP-H问题不⼀定是NP问题，所以有⼀部分NP-H问题是NP,有⼀部分不是，这样整个概念相互包含与相交的逻辑就出来

了，如下：

因此说了这么多，个⼈认为为什么要判断⼀个问题是哪类问题，原因在于，它有助于让我们在决⼼实现这类问题之前对问题的难易程度进⾏

⼀个有效的判断。如果⼀个问题是⼀个NP难问题，众所周知我们是不⼀定能够找到最优解的，有时候持有次优解即可。如果⼀个问题连NP

问题都不是，也就是说我在多项式时间内连验证它都很费劲，⼜谈何解决出来呢？这类问题就不⼤有研究的必要了；

证明思路

前⾯的概念留了⼀个点，说NP-H问题和NPC问题都是所有NP问题可以约化到的，那么究竟什么是约化？我了解到的：若B能解决A，那么

就说A可以约化到B，也就是说，B是⼀个复杂度⽐A更⾼的算法，B通过某种特殊情况（简化），可以变成A问题，⽐如B问题是⼆元⼀次⽅

程，A问题是⼀元⼀次⽅程，当B问题，y=0时，它就转变成了⼀元⼀次问题。也就是说B问题能解决A，那么就说A问题可以约化到B；

那说了这么多，NPC的或者NP-H问题的证明思路究竟是什么呢？⾸先我要先判断⼀下这个问题本⾝是不是NP问题（给出⼀个解能否在多项

式时间内验证），然后找到⼀个已知的NPC问题去约化到这个问题，因为我去验证⼀个问题，把所有NP问题都约化⼀遍到我这个问题上不

太可能，⽽NPC问题本⾝的定义就是所有NP问题可以约化到它，那我拿⼀个已知的NPC问题，去验证这个NPC问题可以约化到它，即

所有NP问题->已知的NPC问题->亟待解决的新问题；

这样，也就简化了我去验证⼀个新问题是不是NPC问题的⽅式；

证明是NP-Complete问题：证明是NP-Hard问题：

①证明本⾝是NP问题；①⽆需证明本⾝是NP问题；

②证明⼀个已知的NPC问题能约化到它②证明⼀个已知的NPC问题能约化到它；

常见例⼦

说了这么多，再来两个例⼦来巩固⼀下：

⾸先是⼀个诱导⼦图的问题，问题描述在第⼀⾏，那么想证明这个问题是不是NPC问题（是NPC就⼀定是NP-H了），⾸先判断它是不是

NP问题，那么给出⼀个⼦图包含K个点，问你是否最少包含l条边，很容易就能验证，即在多项式时间内可以验证，是NP问题。

其次，找到⼀个已知的NPC问题，验证这个已知的NPC问题可以约化到这个新问题，那么就能证明他是NPC问题了（即找到⼀个特殊情况

把这个问题简化到已知的NPC问题）

那么当l=时，该问题就变成了找⼀个K⼤⼩的完全⼦图（因为完全⼦图边和顶点的关系就是），⽽找完全⼦图的问题也

称Clique问题，是⼀个已知的NPC问题，那么通过设定l的特殊取值，将待解决问题转化成了现有NPC问题，即由⼀个NPC问题约化⽽来，

本例得证；

2.

IntheHITTINGSETproblem,wearegivenafamilyofts{S1,S2,...,Sn}andabudgetb,andwewishtofindatH

ofsize≤bwhichinterctverySi,rwords,wewantH∩Si≠∅foralli.

ShowthatHITTINGSETisNP-complete.

⼤概的意思就是这是⼀个碰撞集问题，这个集合H跟Si的各个集合都相交：

然后来证明他是⼀个NPC问题：

①⾸先证明它是⼀个NP问题，像我上图⼀样，如果给出了⼀个集合H，问你它是否跟所有的Si都相交，那么这是在多项式时间内可以验证

的；即是NP问题；

②证明⼀个已知的NPC问题可以约化到它：

当我把Si集合特殊化，即我把每条边当成⼀个Si，集合的元素就是每条边的两端，更改后图如下：

然后把问题变成，找该图中的最⼩顶点覆盖问题（Vertexcover），即找到的集合包含图中每条边的⾄少⼀端。这样也满⾜了我的集合H和

所有Si集合都相交（将Si集合特化成⼀条边的作⽤），那么我亟待解决的问题就特化成了已知的NPC问题——最⼩顶点覆盖问题。那么本例

得证；

21个常见NPC问题

既然现有的⽅式是找到⼀个已有的NPC问题去验证我要验证的新问题，那么知道了解现有的NPC问题就变得很重要，下⾯列举了常见的

NPC问题，⽽每个⼦主题（往后错⼀格）代表这我可以由前⾯的主题约化⽽来：

可以看到，这些问题约化来约化去，都是有⼀个初始问题的，因为⼀个问题由另⼀个已知的NPC问题约化⽽来，那么第⼀个NPC问题是怎

么来的？那就要⽤到NPC问题的本⾝定义了：所有的NP问题可以约化到它；

这个⽅式就是经典的SAT问题，由上图也可以看到，这些已有的NPC问题它的最开始，都是⽤SAT问题证明的；

原理论证

证明了所有的算法都是可以编码为booleanformula（布尔型）问题，这意味着所有算法都可以使⽤SAT去求解，因为他们本质上就

是booleanformula问题。

对于任意的boolearnfoumula写成以下标准式：

(..∨...∨..)∧(..∨...∨..)∧...

SAT:如何取值，使式⼦为真？或根本

不存在⼀个取值使式⼦为真。

这些话是我做的ppt⾥写的，直接拷过来，意思就是，这所有算法⽆外乎就是在⼀个给定集合中找到解，或者⽆解，⽽这些算法的选择，条

件等等都是可以编码为布尔型，⽤合取范式的⽅式表述这个算法的情况，算法有解，就代表合取范式为真，算法⽆解，就代表这个式⼦取值

为假。

具体还是看例⼦，⽤SAT模型去证明我上⾯所说的Clique问题：

⾸先看这个图，我要找它的k=3的clique也就是完全⼦图，答案先放在这（b、c、d）

那现在将他编码为布尔型，任意编码，但边代表着我的相邻节点必须可以同时为真，像a，b可以同时取值为X1，X2，但不能同时取值X1

和，然后图就变成下图：

编完码后，将其写成SAT的合取范式模型，这⾥因为k=3，所以合取范式⾥的析取范式个数为3，搭配是任意的：

写完后，找到⼀个k=3的clique，就变成了找到这个合取范式为真的情形。是单独的，所以它必须为真，那么X1就是假，那X2就必须

为真，为假，那么X3就必须为真，由此得出，编码bcd为真，即k=3的clique找到了；

以上就是NP问题的概念+证明逻辑+例⼦，当然⾃⼰只是浅显的学习，如果有错误或者论证思路不严密，还望赐教；

注：我这⾥⼀直再说NPCNPC，因为NPC是包含在NP-Hard问题⾥的，很多⼈所讲的这个问题是np难的，其实就是NPC问题，因为NPC

⽐np难多了⼀个问题本⾝是NP的，如果这个问题你连验证都验证不了，⼜谈何解决呢？