多项式与非多项式时间复杂性

多项式时间复杂度，是次方项和 logn 项的时间复杂度非多项式时间复杂度，是幂函数项和阶乘项

多项式算法不一定更快，还和问题规模等相关，但是当规模足够大时，多项式算法会更快

易解问题和难解问题 易解问题：可在多项式时间内求解难解问题：不能在多项式时间内求解

例如 TSP 问题是拿求解的问题

P 问题

是一类能够用确定的算法在多项式时间内求解的可判定问题

这类问题也称为多项式类型确定性算法：运行多次结果是一样的；不确定算法如随机算法

可判定问题 image.png|500

这个代码在做出决定之后，永远给出相反的动作，你永远选不对，所以他是不可判定问题

NP 问题

是一类能够用不确定算法在多项式时间内求解的可判定问题

在确定性计算模型下多项式时间可验证的可判定问题这个问题包括两部分，第一部分随机化的取猜答案；第二部分能够多项式时间内验证问题的正确性 NP 的 N 是不确定算法的描述 $N \subseteq NP$ : N 问题属于 NP 问题（N 问题可以都可以使用随机化算法解决？）

一个可判定问题 D，满足

这里的归约就是把问题转化为 D 问题，D 问题就被称为 NP 完全问题

NPC 问题的意义 有一个 NPC 问题找到多项式时间的解法，则全部解决（应该是全部能够转换成 D 问题的所有 NP 问题都能解决）

不浪费时间取寻找有效算法

找近似算法或特例算法

注意一些看起来简单的问题也是 NPC 问题

目前为止，没有一个 NPC 算法找到多项式时间复杂度的解法

NP 完全与 NP 难的区别

NP 完全定义：问题 L 是 NP 完全的当且仅当：

就是 NP 问题归约之后变成 NP 完全问题

NP 难定义：问题 L 满足上述性质 2，但不满足性质 1（里面既有 NP，又有其他的）根据定义可得： $NPC = NP \cap NP$ 难

NP 完全问题家族

从上到下逐渐变难 CLQUE: 最大团问题 VERTEX-COVER：顶点覆盖问题 SUBSET-SUM：子集和问题 HAM-CYCLE: 汉密尔顿回路问题 (城市间找一条环路) TSP：旅行商问题

P、NP、NPC\NP 难问题之间的关系

第 1，2 条正确第 3，4 条不认同