隨機複雜度類別
一句話解釋
隨機演算法擴展了複雜度理論：RP 允許單向錯誤、BPP 允許雙向錯誤、ZPP 是 Las Vegas，都在多項式時間內。
Turing Machine 基礎
計算模型
Deterministic Turing Machine (DTM)
組成：
- 無限長紙帶（tape）
- 讀寫頭（head）
- 有限狀態控制（finite control）
- 轉移函數 $\delta(q, a) = (q’, a’, D)$
- $q$: 當前狀態，$a$: 讀到的符號
- $q’$: 新狀態，$a’$: 寫入符號，$D$: 移動方向
Probabilistic Turing Machine (PTM)
加入隨機選擇：
轉移函數變成機率分佈：
$$
\delta(q, a) = \{(q'_1, a'_1, D_1, p_1), (q'_2, a'_2, D_2, p_2), \dots\}
$$
其中 $\sum_i p_i = 1$
等價於：機器可以「擲硬幣」來決定下一步。
傳統複雜度類別
P 與 NP
P（Polynomial Time）
定義： 可在**確定性**多項式時間內解決的決策問題集合。
$$
\text{P} = \bigcup_{k \geq 0} \text{DTIME}(n^k)
$$
範例：
- 最短路徑（Dijkstra）
- 排序（Merge Sort）
- 線性規劃（Ellipsoid Method）
NP（Nondeterministic Polynomial Time）
定義： 可在多項式時間內**驗證**解的決策問題集合。
等價定義：**非確定性** Turing Machine 可在多項式時間內解決。
$$
\text{NP} = \bigcup_{k \geq 0} \text{NTIME}(n^k)
$$
範例：
- SAT（Boolean Satisfiability）
- TSP（Traveling Salesman，判定版本）
- Graph Coloring
co-NP
定義： 補問題（complement）在 NP 的問題集合。
$$
L \in \text{co-NP} \iff \bar{L} \in \text{NP}
$$
範例：
- UNSAT（不可滿足性）
- TAUTOLOGY（永真式）
關係
P ⊆ NP
P ⊆ co-NP
P = NP ∩ co-NP （已知）
未知： P ?= NP, NP ?= co-NP
P ⊆ co-NP
P = NP ∩ co-NP （已知）
未知： P ?= NP, NP ?= co-NP
隨機複雜度類別
RP, co-RP, ZPP, BPP
RP（Randomized Polynomial Time）
定義： Monte Carlo 演算法，**單向錯誤**（one-sided error）。
對語言 $L$：
- 若 $x \in L$：$\Pr[\text{Accept}] \geq \frac{1}{2}$
- 若 $x \notin L$：$\Pr[\text{Accept}] = 0$（**不會誤判**）
特性：
- Yes 答案一定對
- No 答案可能錯（但重複可降低錯誤率）
範例：質數測試（某些版本）
- 若 $n$ 是質數：高機率通過測試
- 若 $n$ 是合數：一定不通過測試
co-RP
定義： RP 的補類別。
對語言 $L$：
- 若 $x \in L$：$\Pr[\text{Accept}] = 1$
- 若 $x \notin L$：$\Pr[\text{Reject}] \geq \frac{1}{2}$
特性：
- No 答案一定對
- Yes 答案可能錯
ZPP（Zero-error Probabilistic Polynomial）
定義： Las Vegas 演算法，**期望**多項式時間。
$$
\text{ZPP} = \text{RP} \cap \text{co-RP}
$$
特性：
- 總是給出正確答案
- 運行時間隨機，期望多項式
範例：Randomized Quicksort
期望時間 $O(n \log n)$，總是正確排序。
BPP（Bounded-error Probabilistic Polynomial）
定義： Monte Carlo，**雙向錯誤**（two-sided error）。
對語言 $L$：
- 若 $x \in L$：$\Pr[\text{Accept}] \geq \frac{2}{3}$
- 若 $x \notin L$：$\Pr[\text{Reject}] \geq \frac{2}{3}$
關鍵： 錯誤率可透過重複降到任意小。
💡 為什麼用 2/3？
任何常數 $> 1/2$ 都可以（透過 amplification 達到任意接近 1）。
2/3 只是慣例，計算方便。
PP（Probabilistic Polynomial Time）
定義： 成功率 $> 1/2$（但可以非常接近 1/2）。
- 若 $x \in L$：$\Pr[\text{Accept}] > \frac{1}{2}$
- 若 $x \notin L$：$\Pr[\text{Accept}] < \frac{1}{2}$
問題： 錯誤率可能是 $1/2 - 1/2^{n^{100}}$，無法有效 amplify！
類別關係圖
已知關係：
P ⊆ ZPP ⊆ RP ⊆ NP
P ⊆ ZPP ⊆ co-RP ⊆ co-NP
RP ⊆ BPP ⊆ PP
co-RP ⊆ BPP ⊆ PP
BPP ⊆ PSPACE
猜測（未證明）：
P = BPP （多數人相信）
RP ≠ NP
P ⊆ ZPP ⊆ RP ⊆ NP
P ⊆ ZPP ⊆ co-RP ⊆ co-NP
RP ⊆ BPP ⊆ PP
co-RP ⊆ BPP ⊆ PP
BPP ⊆ PSPACE
猜測（未證明）：
P = BPP （多數人相信）
RP ≠ NP
比較表
| 類別 | 模型 | 錯誤類型 | 範例 |
|---|---|---|---|
| **P** | 確定性 | 無錯誤 | 排序、最短路 |
| **RP** | 隨機 | 單向（Yes 對） | 質數測試（某些） |
| **co-RP** | 隨機 | 單向（No 對） | 多項式等價測試 |
| **ZPP** | 隨機 | 無錯誤（Las Vegas） | Randomized Quicksort |
| **BPP** | 隨機 | 雙向（可 amplify） | 多項式等價測試 |
| **PP** | 隨機 | 雙向（難 amplify） | Majority-SAT |
Amplification：降低錯誤率
重複執行
BPP 的 Amplification
原始： 錯誤率 $\leq 1/3$
重複 $k$ 次，取多數決（Majority Vote）：
錯誤率降為：
$$
\epsilon_k \leq e^{-\Omega(k)}
$$
具體地，Chernoff Bound 給出：
$$
\epsilon_k \leq 2^{-\Omega(k)}
$$
範例： 重複 $k = O(\log n)$ 次 → 錯誤率 $\leq 1/n^c$（多項式小）
RP 的 Amplification
原始： 成功率 $\geq 1/2$
重複 $k$ 次：
失敗率（全部失敗）：
$$
(1/2)^k \leq 2^{-k}
$$
範例： 重複 $k = O(\log n)$ 次 → 失敗率 $\leq 1/n^c$
Coin Transformation
硬幣轉換
問題
只有有偏硬幣（bias coin），如何模擬公平硬幣？
Von Neumann Trick
假設： 硬幣正面機率 $p \in (0, 1)$（未知）
方法：
1. 擲兩次，觀察結果
2. 若 $(H, T)$ → 輸出 $0$
3. 若 $(T, H)$ → 輸出 $1$
4. 若 $(H, H)$ 或 $(T, T)$ → 重擲
分析：
$$
\Pr[(H,T)] = p(1-p) = \Pr[(T,H)]
$$
所以輸出 0 和 1 的機率相等（$1/2$）！
期望擲幣次數：
$$
\mathbb{E}[\text{擲幣次數}] = \frac{2}{2p(1-p)} = \frac{1}{p(1-p)}
$$
逆問題：模擬有偏硬幣
用公平硬幣模擬機率 $p = k/2^n$ 的事件：
- 擲 $n$ 次公平硬幣，得二進位數 $m \in [0, 2^n-1]$
- 若 $m < k$，輸出 1；否則輸出 0
總結
隨機複雜度類別擴展了計算理論：
- RP： 單向錯誤（Yes 對），如質數測試
- co-RP： 單向錯誤（No 對）
- ZPP = RP ∩ co-RP： 無錯誤但時間隨機（Las Vegas）
- BPP： 雙向錯誤，但可 amplify（最廣泛使用）
- PP： 雙向但難 amplify（較不實用）
大猜想： P = BPP（隨機不真的增加計算能力？）
參考資料
- Arora & Barak, Computational Complexity: A Modern Approach, Chapter 7
- Goldreich, Computational Complexity: A Conceptual Perspective
- Sipser, Introduction to the Theory of Computation, Chapter 10