六、算法復(fù)雜性初步

---

重要的復(fù)雜性類

• $P$ 的定義

  • 多項式時間內(nèi)可解的問題

  • 若$L\in P$，則存在確定性多項式時間的圖靈機$M$，使得
    $$M(x)=1?x\in L$$

• $NP$ 的定義

  • 多項式時間內(nèi)可驗證驗證解的正確性

  • （表示非確定性多項式時間而不是非多項式時間）

  • 若 $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$能夠在多項式時間內(nèi)驗證$x\in M$

• $NP?hard$

  • 若一個問題屬于 $NP?hard$，那么它可以在多項式時間內(nèi)規(guī)約成 $NP$ 問題

• $NP?complete$

  • 是$NP$和$NP?hard$的交集，即 $NPC=NP\cap NPH$
  • $NPC$是$NP$中最難的問題，如果找到多項式時間解決$NPC$，那么$P=NP$

---

SAT 問題

定義：給定一個布爾邏輯表達式，判斷是否存在一個布爾變量賦值，使得整個表達式的值為真。

合取范式（CNF）：一種布爾邏輯表達式的標準化形式，若干個句子合取（AND），每個句子中若干個文字析取（OR）

例如，以下一個CNF公式：
$$(?a_1\vee a_2)\wedge (?a_1\vee a_3\vee a_4)\wedge (a_1\vee ?a_2\vee a_3\vee ?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 ?$

當n>2，n-SAT問題就是NP-hard的。任何n-SAT都可以通過引入新變量的方法轉(zhuǎn)化為3-SAT問題。

---

隨機化算法

ZPP類型

• 保證一定能找到正確答案
• 需要多次運行，可以在期望的多項式時間內(nèi)找到結(jié)果
• 即：保證正確性，運行時間隨機性
• 如：隨機化快速排序、隨機化選擇算法

BPP類型

• 不保證得到正確答案，結(jié)果可能出錯
• 時間是確定的多項式時間
• 即：時間復(fù)雜度好，結(jié)果不好
• 如：矩陣恒等式測試

---

6.1 證明：$P?NP$

證明：

• 對于$P$問題的圖靈機$M$，構(gòu)造另一個圖靈機$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 }$是確定性多項式圖靈機，結(jié)合$NP$問題定義，存在$w^{\prime }\in {0,1}^{ploy(n)}$，$M^{\prime }(x,w^{\prime })=1$，驗證解是否正確。所以該$P$問題也是一個$NP$問題，所以$P?NP$。

---

6.2 證明: 如果存在 $NP$ 難的問題 $\Pi \in P$，則 $P=NP$

證明：

• 根據(jù) $\Pi \in P$，得$\Pi$在多項式時間可解決
• 根據(jù) $NP?hard$ 定義，所有$NP$問題$F$可在多項式時間內(nèi)規(guī)約到$\Pi$，即$F\in NP$，有$F{\le }_p\Pi$
• 所以$F$在多項式時間轉(zhuǎn)化為$\Pi$，再多項式求解$\Pi$，整個過程是多項式時間完成的，所以$NP?P$
• 又已知$P?NP$，所以證得$P=NP$。

---

6.3 證明：如果$NP=P$，則單向陷門不存在。

• 假設(shè)算法Invert用來尋找函數(shù)$f$的逆映射：利用一系列語言$Li$，表示是否存在$w$使得$y=f(z||w)$
• 根據(jù)文本內(nèi)容，$Li$屬于$NP$，同依據(jù)條件，也屬于$P$
• 如果$P=NP$，那么該算法能在多項式內(nèi)求解，即找到了函數(shù)$f$的逆映射，也就是找到$x$使得$f(x)=y$
• 綜上，若$N=NP$，多項式時間可破壞單項函數(shù)的不可逆的性質(zhì)，則單向陷門不存在

---