多项式复杂度
NP 问题中的 P 意思是 Polynomial，意为多项式复杂度。其中，O(1), O(log(n)), O(n), O(nlog(n)), O(n^2), … O(n^a) 这一类的复杂度（从小到大顺序）的问题是多项式复杂度的。他们的特点是，问题的复杂度不会因为 n 的增大而增大。相反，O(a^n) 和 O(n!) 这类问题因为问题的复杂度会因为 n 增大而增大，所以认为不是多项式的。举 2 个例子，
P 问题
1
2
3
4
5
6
7
8
9
10
11
| 找中位数问题
在一个数组 arr = [13, 8, 1, 2, 4, 6, 11] 中，我们要找到数组的中位数。
解答
需要对这个数组排序，然后找到 [1, 2, 4, 6, 8, 11, 13] 中下标是 (n + 1) / 2 的数字，也就是 6。所以解答这个问题的复杂度是 O(nlog(n))。
验证
假设有一个解答是 3，要判断这个数是否是这个问题的答案。那么只需要判断数组中大于 3 和小于 3 的数的个数是否相等。所以验证这个解答是否正确的复杂度是 O(n)。
|
这种解答复杂度和验证复杂度都是 P 的就认为是 P 类问题。
NP Complete 问题
1
2
3
4
5
6
7
8
9
10
11
12
13
| 3 - SAT 问题
如果有 a, b, c, d, e, f 都为 boolean 类型的变量。是否存在这样的一组 a, b, c, d, e, f 满足
(a || b || c) && (!a || b || f) && (!e || d || f) == true
解答
假设 0 表示 false， 1 表示 true 那么就需要暴力采用枚举的方式去找到这组符合最终结果的值。这样的复杂度是 2^6。也就是说，当输入的变量个数为 n 的时候，复杂度就是 2^n。所以这种问题解决的复杂度是 O(a^n)，这样的问题就是 NP 问题。
验证
假设有一组解答是 0, 1, 1, 1, 0, 1。要判断是否是这个问题的答案，只需要带入进行计算即可。以验证这个解答是否正确的复杂度是 O(1)。（满足 P）
|
这种解答复杂度为非 P 而验证复杂度为 P 的就认为是 NP Complete 问题。
N == NP ?
回过头看，
- 当验证一个解答是否是这个问题的正确答案的复杂度是 P 的时候，这个问题是 NP 问题
- 在 1 的基础上，我们发现如果解决这个问题的复杂度是 P 的时候，这个问题是 P 问题
- 在 1 的基础上，我们发现解决这个问题的复杂度不是 P 的时候，这个问题是 NP Complete 问题
当我们研究这个世界的问题的时候，有人认为所有的 NP 问题都是 P 问题；有人则认为一定不是所有的 NP 问题都是 P 问题。在计算机科学的颠峰上，人类的智慧一直在为证明 N == NP 做出努力。