Creator's World

一、时间复杂度

1. 多项式复杂度：规模 $n$在底数位置上或者常数级复杂度。如 $O(1)、O(n)、O(n\log n)、O(n^2)$ 等。

2. 非多项式级复杂度：规模 $n$ 在指数位置上的复杂度。如 $O(2^n)、O(n!)$。

二、P 问题

1. 定义：存在 多项式复杂度算法的问题。

三、NP 问题

1. NP 问题 不是 非 P 问题。

2. 定义：一个问题的一个解可以用多项式级复杂度 检验，它就是 NP 问题。

3. 找不到多项式复杂度解的（非 P 问题）不一定 是 NP 问题，因为有可能无法在多项式复杂度中检验一个解。

4. P $\in$ NP。

四、NP-hard 问题

1. 定义：如果有一个问题可以使所有 NP 问题在多项式复杂度内 归纳 到它（相当于转化到它），那么它就是 NP-hard 问题。若难度有上线，解决 NP-hard 问题的难度就是这个上限，这是名字的由来。

2. NP-hard 问题 不一定 是 NP 问题。

3. 常见的 NP-hard 问题有 停机问题。

五、NPC 问题

1. 定义：一个 NP 问题 可以使所有 NP 问题在多项式复杂度内归约到它，那它就是 NPC 问题。

2. NPC 是 NP 和 NP-hard 的交集。

3. 常见的 NPC 问题有 3-SAT、旅行商问题 等。