NPC问题
P, NP, NPC的关系
- 讨论这些问题需要先清楚决定性问题和非决定性问题
- 决定性问题就是回答yes or no的问题, 比如存不存在一个解使得xxx.
- 非决定性问题就是what问题, 比如满足这个条件的值是最小是几.
- 所有问题讨论都是针对决定性问题的,没有讨论非决定性问题的.
- P是指在多项式时间内能够找到算法的决定性问题
- 比如贪心算法,基本上用O(n)就搞定了
- 或者排序算法(分治法),O(n^2)或者O(nlogn)
- 动态规划 O(nm) O(n^2)
还有什么算法是P问题?
- NP问题是是指不能在多项式时间内找到算法的决定性问题
- 这里先不举例后面有例子
- 但是可以肯定的是,我们之前学到的算法都不是符合这样的问题,brute force, exhaustive search除外.
- 要了解NPC需要先了解什么叫归约 $leq_P$
- 归约就是,一个问题通过多项式时间转化可以变成另外一个问题
举例
- NPC问题 是指最难的NP问题
- 什么样的问题算是最难的?
- 就是所有的NP问题都可以归约到这个问题
- 常见的NPC问题(考试应该会用其中的一种进行归约)
- 图同构
貌似没讲? - 布尔满足性问题 SAT
- SAT问题是指: 给一个函数$f=(a,b,c)$能否找到一个abc解,使得函数结果为真
- 华容道问题(没讲) N-puzzle
- 背包问题
??? - 汉密尔顿循环(没讲)
- 旅行推销员, traveling salesman problem
如果没猜错,应该是 有一堆城市(图) 找到一个方法可以一次走遍所有的城市且只去一次.- 不同于一笔画,一笔画是覆盖所有的边
- 子图加和总集(没讲)
- 分团问题 clique problem
- 一个图中,是否存在K个顶点的完全子图(完全子图是几个顶点组成的子图是完全图)
- 顶点覆盖问题 vertex cover problem
- 一个图中是否存在K个顶点能够覆盖所有的边
- 独立顶点集问题 independent set problem
- 一个图中是否存在K个顶点,使得他们之间没有互相连接(不存在两个点相连的边)
- 图着色 graph coloring problem
- 类似四色定理,一个图中是否存在用K个颜色能涂满所有的点,并保证相邻的点的颜色不一样.
- 图同构
- 除了P, NP, NPC科学家们还脑洞想出了一些其他问题
- 简单的方法就是规约
- 但是想到一个问题P可以被问题A规约是很难的
- 所以这里列出了一些常见问题规约的方法
- 对于能否找到k的non-overlapping的问题，可以使用int set的方法
时间复杂度和NP问题的在现实世界中的关系
- 不是所有的P问题在现实中都可以解的.
- 一般来说O(n^2)就已经很大了,(当N足够大的时候). O(nlogn)是可以接受的.但是有些P问题是O(n^10)的啊,这种肯定解不了.
- 而别的NP也不是完全不可解比如O(2^n) n够小的话还是可以的(哪有那么多超大N是需要计算的).
- 下面列出一些现实中能解的和不能解得问题
|yes|probably No|
|—-|—-|
|shortest path|longest path|
|matching| 3d matching|
|min-cut| max-cut|
|2-SAT|3-SAT|
|四色定理|三色|
|Bipartite vertex cover|Vertex cover|
|Primality testing|Factoring|
近期评论