【算法】复杂性理论初步

六、算法复杂性初步

---

重要的复杂性类

• $P$ 的定义

  • 多项式时间内可解的问题

  • 若$L\in P$，则存在确定性多项式时间的图灵机$M$，使得
    $$M(x)=1⟺x\in L$$

• $NP$ 的定义

  • 多项式时间内可验证验证解的正确性

  • （表示非确定性多项式时间而不是非多项式时间）

  • 若 $L\in NP$，则存在确定性多项式时间的图灵机$M$，使得
    x ∈ L ⟺ ∃ w ∈ { 0 , 1 } p l o y ( n ) s . t . M ( x , w ) = 1 x∈L⟺\exist w∈\{0,1\}^{ploy(n)}\ \ s.t.\ M(x,w)=1 x∈L⟺∃w∈{0,1}ploy(n)  s.t. M(x,w)=1
    注：如果$x\in L$，那么存在一个证书$w$，使$M$能够在多项式时间内验证$x\in M$

• $NP-hard$

  • 若一个问题属于 $NP-hard$，那么它可以在多项式时间内规约成 $NP$ 问题

• $NP-complete$

  • 是$NP$和$NP-hard$的交集，即 $NPC=NP\cap NPH$
  • $NPC$是$NP$中最难的问题，如果找到多项式时间解决$NPC$，那么$P=NP$

---

SAT 问题

定义：给定一个布尔逻辑表达式，判断是否存在一个布尔变量赋值，使得整个表达式的值为真。

合取范式（CNF）：一种布尔逻辑表达式的标准化形式，若干个句子合取（AND），每个句子中若干个文字析取（OR）

例如，以下一个CNF公式：
$$(\neg a_1\vee a_2)\wedge (\neg a_1\vee a_3\vee a_4)\wedge (a_1\vee \neg a_2\vee a_3\vee \neg a_4)$$
注：存在一种赋值，使其中一个句子为真，整个CNF即为真。

2-SAT问题：每个子句恰好包含2个文字。$P$ 类问题。

3-SAT问题：每个子句恰好包含3个文字。$NP-complete$ 问题。

• 例如：$(l_1\vee l_2\vee l_3)\wedge (l_4\vee l_5\vee l_6)\wedge \cdots$

当n>2，n-SAT问题就是NP-hard的。任何n-SAT都可以通过引入新变量的方法转化为3-SAT问题。

---

随机化算法

ZPP类型

• 保证一定能找到正确答案
• 需要多次运行，可以在期望的多项式时间内找到结果
• 即：保证正确性，运行时间随机性
• 如：随机化快速排序、随机化选择算法

BPP类型

• 不保证得到正确答案，结果可能出错
• 时间是确定的多项式时间
• 即：时间复杂度好，结果不好
• 如：矩阵恒等式测试

---

6.1 证明：$P\subseteq NP$

证明：

• 对于$P$问题的图灵机$M$，构造另一个图灵机$M^{\prime }$：输入是$w$和$x$，对于相同的$x$有相同的输出，$w$对输出无影响
• 当$x\in L$时，$M(x)=1$，存在$w^{\prime }\in {0,1}^{ploy(n)}$，$M^{\prime }(x,w^{\prime })=1$
• 当$x\notin L$时，$M(x)=0$，对于任意的$w$，$M^{\prime }(x,w)=0$
• 显然$M^{\prime }$是确定性多项式图灵机，结合$NP$问题定义，存在$w^{\prime }\in {0,1}^{ploy(n)}$，$M^{\prime }(x,w^{\prime })=1$，验证解是否正确。所以该$P$问题也是一个$NP$问题，所以$P\subseteq NP$。

---

6.2 证明: 如果存在 $NP$ 难的问题 $\Pi \in P$，则 $P=NP$

证明：

• 根据 $\Pi \in P$，得$\Pi$在多项式时间可解决
• 根据 $NP-hard$ 定义，所有$NP$问题$F$可在多项式时间内规约到$\Pi$，即$F\in NP$，有$F{\le }_p\Pi$
• 所以$F$在多项式时间转化为$\Pi$，再多项式求解$\Pi$，整个过程是多项式时间完成的，所以$NP\subseteq P$
• 又已知$P\subseteq NP$，所以证得$P=NP$。

---

6.3 证明：如果$NP=P$，则单向陷门不存在。

• 假设算法Invert用来寻找函数$f$的逆映射：利用一系列语言$Li$，表示是否存在$w$使得$y=f(z||w)$
• 根据文本内容，$Li$属于$NP$，同依据条件，也属于$P$
• 如果$P=NP$，那么该算法能在多项式内求解，即找到了函数$f$的逆映射，也就是找到$x$使得$f(x)=y$
• 综上，若$N=NP$，多项式时间可破坏单项函数的不可逆的性质，则单向陷门不存在

---