多项式复杂度

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),非 P。

验证

假设有一组解答是 0, 1, 1, 1, 0, 1。要判断是否是这个问题的答案,只需要带入进行计算即可。以验证这个解答是否正确的复杂度是 O(1)。(满足 P)

这种解答复杂度为非 P 而验证复杂度为 P 的就认为是 NP Complete 问题。

N == NP ?

回过头看,

  1. 当验证一个解答是否是这个问题的正确答案的复杂度是 P 的时候,这个问题是 NP 问题
  2. 在 1 的基础上,我们发现如果解决这个问题的复杂度是 P 的时候,这个问题是 P 问题
  3. 在 1 的基础上,我们发现解决这个问题的复杂度不是 P 的时候,这个问题是 NP Complete 问题

当我们研究这个世界的问题的时候,有人认为所有的 NP 问题都是 P 问题;有人则认为一定不是所有的 NP 问题都是 P 问题。在计算机科学的颠峰上,人类的智慧一直在为证明 N == NP ? 做出努力。