初赛备考干货：P问题，NP问题，NP-hard问题，NPC问题，傻傻分不清楚？

## 前言 P/NP/NPC问题在2012年左右曾经火了一阵，如果你做过2012年和2013年的提高组真题的话，你会发现，那两年每年都有一道这种问题的**多选题**。~~（不过之后就凉凉了）~~，所以这类问题还是有必要了解一下的。 **反正重要的知识点就这么几句话，我都划重点了，其他都是瞎扯可以无视的啦QAQ**（这句不是重点啊） ## 零、预备内容：时间复杂度 时间复杂度分为两种：多项式级复杂度和非多项式级复杂度 其中多项式级复杂度是指规模$n$在底数位置上的或者常数级的复杂度 比如说$O(1)$、$O(n)$、$O(nlogn)$或者$O(n^2)$等等 而非多项式级复杂度则是规模$n$在指数位置上的复杂度 比如说$O(2^n)$或者$O(n!)$ 这么区分的原因是因为这两种复杂度是天差地别的，后者远大于前者。 举个例子：当$n=10$的时候 ```plain O(1)=1 O(N)=10 O(N^2)=100 O(2^N)=1024 O(N!)=3628800 O(N^N)=10000000000 ``` ## 一、P问题的引入 自从发现了这两种复杂度之后，有些人就开始想了：“多项式复杂度好棒棒啊！如果所有问题都有多项式复杂度的解法就好了啊！” 这个时候，图灵跳了出来，丢了一个停机问题，人们吃惊地发现，这个问题甚至没有正确的解决方法，于是上面的flag就这样子GG了。 所以又有人来说了：“那能解的问题是不是一定有多项式解法呢？” 于是又来了一个问题：请解决3-SAT问题。 然后不用想了，又GG了。 这个时候脸被打得生疼的科学家们发现，他们有必要划分一下这些问题，以免再被打脸，因此他们就提出了P问题(Polynomial problem)(P是多项式的简写) >**定义P问题为存在多项式复杂度算法的问题** ## 二、NP问题的引入 有了P问题，科学家想了想，那我们就搞个不是P问题的专有名词，专指找不到多项式复杂度的问题（非P问题）不就行了吗？ ~~然后他们就提出了NP问题，全剧终~~ 嗯，事情没有这么简单，如果你要向上面那样想，你就可能要凉凉了。 >**NP问题不是非P问题** 上面那种NP问题的定义会变得非常爆炸，因为你有时候并不能证明这个问题是不是一定没有多项式解，也就是说不确定现在这个不存在多项式复杂度的问题在未来也不存在多项式复杂度解法，显然这些问题你既不能归入P又不能归入NP，所以你还要再定义一个别的东西来表示他们，反正这个定义GG了 回顾之前所说，我们一开始的希望是找到多项式复杂度的解法，接着才会去考虑划分这些问题，所以我们的划分理应去往这个方向靠。 那么可以将NP问题定义为还不存在多项式复杂度解法的问题，用未解代替无解.~~(这体现了定义的科学性、准确性、严谨性、平实性、周密性)~~ 以及我们的目标是找到NP问题的多项式解法，所以我们要使NP问题有可能能解，显然要去掉所有能证明无多项式解的问题，如果一个问题的一个解的验证都是非多项式级别的，这个问题就不可能做到多项式级复杂度，因为如果我们连它的一个条件都无法在多项式复杂度中证明，那么就更别谈在多项式复杂度中把他的所有条件都证明出来了。 终于可以给出NP问题(Non-deterministic Polynomial problem)的完全定义了(没错，这个N是不确定的意思) >**一个问题的一个解可以用多项式级复杂度检验，它就是NP问题** 所以有一点值得注意的 >**找不到多项式复杂度解的(非P问题)不一定是NP问题** 因为有些无法在多项式复杂度中检验一个解的问题存在。 同时，这里可以很明显的发现，如果一个问题是P问题，那么他肯定能在多项式时间复杂度内检验任意一组解。于是又可以推出 >**P∈NP** 但是P=NP吗？这是一个世纪难题，反正了解一下有这个问题就行了，初赛不会让你证明的，放心好了。 ## 三、NP-hard和NPC问题的引入 虽然说不用让你去证明P=NP这种鬼畜的东西，但是科学家不断尝试证明的这段历史是没准会考的。(~~毕竟这是一种自强不息的求索精神，很符合二十四字核心价值观~~) 在此之前我们先引入归约的定义 >归约指的是将A问题进行归约后可以用B问题的解决方法解决，也就是把A问题变成B问题解决 NPhard问题是指 >**如果有一个问题可以使所有NP问题在多项式复杂度内归约到它，那么它就是NP-hard问题** 显然如果难度有一个上界的话，解决所有的NP问题归约起来的问题难度肯定就是那个上界，所以这类问题被称为NP-hard。 如果你有了解过停机问题的话，会知道这个问题是不可判的，但是如果把问题理解成输入一个东西到某个程序里，判断他是否会停机，就可以把所有NP问题归约到停机问题上来，所以停机问题是NP-hard，于是 >**NP-hard问题不一定是NP问题** 既然不一定是NP问题那么对我们解决P=NP就没啥用了。 所以科学家又提出了NPC问题： >**一个NP问题可以使所有NP问题在多项式复杂度内归约到它，那么它就是NPC问题** 也就是说如果解决了NPC问题就可以解决所有的NP问题，然后就可以证明P=NP。 常见的NPC问题有3-SAT问题，旅行商问题等等。 这些的证明有兴趣大家可以研究一下。 最后祭上这张图来总结上面知识点之间的联系  接着我们来切几道真题。 ## 四、历年真题 2012.20．以下关于计算复杂度的说法中，正确的有（ ）。 A．如果一个问题不存在多项式时间的算法，那它一定是NP类问题 B．如果一个问题不存在多项式时间的算法，那它一定不是P类问题 C．如果一个问题不存在多项式空间的算法，那它一定是NP类问题 D．如果一个问题不存在多项式空间的算法，那它一定不是P类问题 解析： A 还记得图灵停机问题吗？那是一个NP-hard而不是NP问题 B 这是对的，因为P问题的定义是存在多项式时间的复杂度算法 C、D 时间复杂度和空间复杂度都是复杂度，是等价的。 所以选BD 2013.14. （ ）属于 NP 类问题。 A. 存在一个 P 类问题 B. 任何一个 P 类问题 C. 任何一个不属于 P 类的问题 D. 任何一个在（输入规模的）指数时间内能够解决的问题 解析： 这里考察的知识点是NP问题的定义以及P∈NP 由之前可知任何P问题都是NP问题，同理一定存在一个P问题是NP问题 AB都是对的 C的话我们可以继续用万能的停机问题去反驳他 D考察的是定义，指数时间内能解决不意味着多项式时间能验证解，所以D是错的 所以选AB 那就这样子了，希望对大家有所帮助。