隨機選擇可以簡化算法,但概率保證必須說明涵蓋哪些輸入,以及哪些答案可能出錯。複雜度類別採用的是對輸入的最壞情況保證,概率則是針對算法自身的隨機位元,而不是假設輸入服從某個分佈。
本單元有三個目標。第一,確定概率陳述所描述的究竟是甚麼實驗。第二,定義類別 R P \mathrm{RP} RP 與 B P P \mathrm{BPP} BPP ,並說明其中的常數只是約定,因為獨立重複可以把錯誤降低。第三,區分哪些內容可從第一原理證明,哪些是引入的結果。下文證明了兩個不同的放大論證,一個依賴所引用的集中不等式,另一個則完全是初等的。若干反例說明了每項假設在何處是必要的。
動機與概率空間
確定性算法在每個輸入上只有一條計算路徑,其正確性是關於該路徑的是非性質。隨機化算法在每個輸入上有許多條路徑,每條對應它可能讀取的一個隨機位元序列。正確性於是變成一個關於良好路徑集合有多大的問題。在陳述任何定理之前,我們必須精確說明樣本空間是甚麼。
設 M M M 為一個隨機化算法,它在長度為 n n n 的輸入上的運行時間,對於每一種隨機位元的選擇,至多為多項式 p ( n ) p(n) p ( n ) 。這樣的算法讀取的隨機位元不會多於 p ( n ) p(n) p ( n ) 個。因此我們可以補齊,並把隨機輸入視為均勻選取的字串 ρ ∈ { 0 , 1 } p ( n ) \rho\in\{0,1\}^{p(n)} ρ ∈ { 0 , 1 } p ( n ) ,並以 M ( x , ρ ) M(x,\rho) M ( x , ρ ) 表示輸入為 x x x 、隨機字串為 ρ \rho ρ 時的輸出。對於固定的輸入 x x x ,接受概率為
Pr ρ [ M ( x , ρ ) = 1 ] = ∣ { ρ ∈ { 0 , 1 } p ( n ) : M ( x , ρ ) = 1 } ∣ 2 p ( n ) . \Pr_\rho[M(x,\rho)=1]=\frac{\left|\{\rho\in\{0,1\}^{p(n)} : M(x,\rho)=1\}\right|}{2^{p(n)}}. ρ Pr [ M ( x , ρ ) = 1 ] = 2 p ( n ) { ρ ∈ { 0 , 1 } p ( n ) : M ( x , ρ ) = 1 } .
這是關於有限集合的計數陳述,因此不需要測度論。以下三個結果貫穿全文。
每個接受概率都是分母為 2 的冪的有理數。
概率附屬於固定的輸入 x x x 。這裏沒有隱藏的輸入分佈,因此這些類別中的保證是分別針對每個輸入的陳述。
獨立重複對應於把字串 ρ 1 , … , ρ r \rho_1,\dots,\rho_r ρ 1 , … , ρ r 串接起來,其中每個字串均勻且獨立地抽取,因此聯合樣本空間是帶有均勻測度的 { 0 , 1 } r p ( n ) \{0,1\}^{rp(n)} { 0 , 1 } r p ( n ) 。獨立性就是這個空間的乘積結構,並不是額外疊加上去的假設。
因此每個保證中都出現三個量詞。全稱量詞遍歷各個輸入。概率遍歷算法自身的位元。運行時間界遍歷所有位元字串,包括運氣不好的字串。丟掉最後一項會改變模型,因為一個在極小部分隨機字串上永遠運行下去的算法,並不是本文所用意義下的多項式時間算法。
錯誤保證
若存在一個隨機化多項式時間算法,它以概率 1 1 1 拒絕 L L L 之外的每個輸入,並以至少 1 / 2 1/2 1/2 的概率接受 L L L 中的每個輸入,則稱語言 L L L 屬於 R P \mathrm{RP} RP 。若存在一個隨機化多項式時間算法,它在每個輸入上以至少 2 / 3 2/3 2/3 的概率返回正確答案,則稱 L L L 屬於 B P P \mathrm{BPP} BPP 。概率是針對獨立的無偏隨機位元而言;時間界對這些位元的每一種選擇都成立。
這些常數只是約定:對於雙側錯誤,任何嚴格大於 1 / 2 1/2 1/2 的固定成功概率都可以被放大。對於 RP,獨立重複並在任何一次運行接受時即接受,既保持零假陽性,又降低假陰性。因此 P ⊆ R P ⊆ B P P \mathrm P\subseteq\mathrm{RP}\subseteq\mathrm{BPP} P ⊆ RP ⊆ BPP :確定性程序只需忽略其隨機位元,而 RP 算法可以先重複固定次數,以達到 BPP 的成功概率門檻。
為兩種錯誤命名會有幫助。假陽性是接受了 L L L 之外的輸入,假陰性是拒絕了 L L L 中的輸入。RP 算法只可能犯假陰性錯誤,而且對 L L L 的每個成員,概率至多為 1 / 2 1/2 1/2 。因此它的答案「接受」永遠可信,而「拒絕」只具提示性。BPP 算法兩種錯誤都可能犯,但在每個輸入上,不論是否為成員,答錯的概率至多為 1 / 3 1/3 1/3 。
設在某個固定輸入上,某算法的每次獨立運行都以至少 2 / 3 2/3 2/3 的概率正確。則對於奇數 r r r ,r r r 次獨立運行的多數結果之錯誤概率至多為 e − r / 18 e^{-r/18} e − r /18 。若重複次數為多項式,運行時間仍然是多項式。
設 X i X_i X i 指示第 i i i 次運行的答案是否錯誤。這些獨立變量取值於 [ 0 , 1 ] [0,1] [ 0 , 1 ] ,且 E [ ∑ X i ] ≤ r / 3 \mathbb E[\sum X_i]\le r/3 E [ ∑ X i ] ≤ r /3 。僅當 ∑ X i ≥ r / 2 \sum X_i\ge r/2 ∑ X i ≥ r /2 時多數才會出錯,這比期望值至少高出 r / 6 r/6 r /6 。Hoeffding 不等式給出的概率至多為 exp ( − 2 ( r / 6 ) 2 / r ) = e − r / 18 \exp(-2(r/6)^2/r)=e^{-r/18} exp ( − 2 ( r /6 ) 2 / r ) = e − r /18 。此處使用的集中不等式未加證明。把多項式運行時間乘以多項式次數的重複,結果仍是多項式。
此論證中的每項假設都有其作用。輸入固定,是因為該界是針對每個輸入的陳述。各次運行相互獨立,才能使用 Hoeffding 不等式。r r r 為奇數,排除了平局,使「多數」有明確定義。錯誤變量 X i X_i X i 不必有相同的分佈,因為只用到 E [ X i ] ≤ 1 / 3 \mathbb E[X_i]\le 1/3 E [ X i ] ≤ 1/3 。若某些運行出錯的概率較小,則期望和較小,差距 r / 2 − E [ ∑ X i ] r/2-\mathbb E[\sum X_i] r /2 − E [ ∑ X i ] 至少為 r / 6 r/6 r /6 ,因此界只會更好。所用形式的 Hoeffding 不等式說的是:對於獨立的 X i ∈ [ 0 , 1 ] X_i\in[0,1] X i ∈ [ 0 , 1 ] ,令 S = ∑ i = 1 r X i S=\sum\limits_{i=1}^r X_i S = i = 1 ∑ r X i ,則對任何 t > 0 t>0 t > 0 ,有 Pr [ S − E [ S ] ≥ t ] ≤ exp ( − 2 t 2 / r ) \Pr[S-\mathbb E[S]\ge t]\le\exp(-2t^2/r) Pr [ S − E [ S ] ≥ t ] ≤ exp ( − 2 t 2 / r ) 。
界如何依賴於優勢
常數 2 / 3 2/3 2/3 並不特殊。把每次運行的成功概率寫成 1 / 2 + δ 1/2+\delta 1/2 + δ ,則 δ \delta δ 稱為相對於隨機猜測的優勢。同一證明給出以下更一般的陳述,這解釋了為何在 B P P \mathrm{BPP} BPP 的定義中,任何嚴格大於 1 / 2 1/2 1/2 的固定成功概率均可取代 2 / 3 2/3 2/3 。
設 0 < δ ≤ 1 / 2 0<\delta\le 1/2 0 < δ ≤ 1/2 。假設 r r r 次獨立運行(r r r 為奇數)中,每次在某固定輸入上都以至少 1 / 2 + δ 1/2+\delta 1/2 + δ 的概率正確。則多數答案錯誤的概率至多為 exp ( − 2 δ 2 r ) \exp(-2\delta^2 r) exp ( − 2 δ 2 r ) 。特別地,若要使錯誤至多為 ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) ,只需取任何滿足 r ≥ ln ( 1 / ε ) / ( 2 δ 2 ) r\ge \ln(1/\varepsilon)/(2\delta^2) r ≥ ln ( 1/ ε ) / ( 2 δ 2 ) 的奇數 r r r 。
設 X i ∈ { 0 , 1 } X_i\in\{0,1\} X i ∈ { 0 , 1 } 指示第 i i i 次運行是否出錯,故 E [ X i ] ≤ 1 / 2 − δ \mathbb E[X_i]\le 1/2-\delta E [ X i ] ≤ 1/2 − δ ,且 S = ∑ X i S=\sum X_i S = ∑ X i 滿足 E [ S ] ≤ r ( 1 / 2 − δ ) \mathbb E[S]\le r(1/2-\delta) E [ S ] ≤ r ( 1/2 − δ ) 。僅當 S ≥ r / 2 S\ge r/2 S ≥ r /2 時多數才會出錯,這比均值至少高出 r / 2 − E [ S ] ≥ δ r r/2-\mathbb E[S]\ge \delta r r /2 − E [ S ] ≥ δ r 。Hoeffding 不等式(未加證明地使用)給出的概率至多為 exp ( − 2 ( δ r ) 2 / r ) = exp ( − 2 δ 2 r ) \exp(-2(\delta r)^2/r)=\exp(-2\delta^2 r) exp ( − 2 ( δ r ) 2 / r ) = exp ( − 2 δ 2 r ) 。令 exp ( − 2 δ 2 r ) ≤ ε \exp(-2\delta^2 r)\le\varepsilon exp ( − 2 δ 2 r ) ≤ ε 並解出 r r r ,得 r ≥ ln ( 1 / ε ) / ( 2 δ 2 ) r\ge\ln(1/\varepsilon)/(2\delta^2) r ≥ ln ( 1/ ε ) / ( 2 δ 2 ) 。取 δ = 1 / 6 \delta=1/6 δ = 1/6 便還原出上一個命題的界 e − r / 18 e^{-r/18} e − r /18 。
反例模式
沒有優勢就無法放大 斷言:對每個單次成功概率,多數表決都會令錯誤下降。設算法無視輸入,輸出它的第一個隨機位元。對每個輸入,它恰以概率 1 / 2 1/2 1/2 答對。取 r = 3 r=3 r = 3 次獨立運行,三個位元中至少兩個答對時多數才答對,概率為 ( 3 + 1 ) / 8 = 1 / 2 (3+1)/8=1/2 ( 3 + 1 ) /8 = 1/2 。由公平位元在 0 ↔ 1 0\leftrightarrow1 0 ↔ 1 下的對稱性,任意奇數 r r r 次運行的多數同樣恰以 1 / 2 1/2 1/2 答對,所以錯誤從不下降。這與優勢界並不矛盾:此處 δ = 0 \delta=0 δ = 0 ,而 exp ( − 2 δ 2 r ) = 1 \exp(-2\delta^2r)=1 exp ( − 2 δ 2 r ) = 1 甚麼也沒說。修正:要求固定的優勢 δ > 0 \delta>0 δ > 0 ;這時 r ≥ ln ( 1 / ε ) / ( 2 δ 2 ) r\ge\ln(1/\varepsilon)/(2\delta^2) r ≥ ln ( 1/ ε ) / ( 2 δ 2 ) 次重複就足夠。
對 δ \delta δ 的依賴在分母中是二次的。若 δ \delta δ 是固定常數,甚至是輸入長度的某個多項式的倒數,則對於任何多項式 q q q ,多項式次數的重複就足以使錯誤達到 2 − q ( n ) 2^{-q(n)} 2 − q ( n ) ,因為 ln ( 1 / ε ) = q ( n ) ln 2 \ln(1/\varepsilon)=q(n)\ln 2 ln ( 1/ ε ) = q ( n ) ln 2 是多項式。若 δ \delta δ 是指數級地小,所需的重複次數是指數級的,此時論證沒有任何用處。
以數值解讀界
像 e − r / 18 e^{-r/18} e − r /18 這樣的界,只有換算成具體的重複次數才有用。以下兩個例子展示如何換算,以及該界有多保守。
設某 BPP 算法在每個輸入上以至少 2 / 3 2/3 2/3 的概率正確。我們想要一個多數表決算法,使其在每個輸入上的錯誤至多為 2 − 20 2^{-20} 2 − 20 。
由多數放大命題,只需 e − r / 18 ≤ 2 − 20 e^{-r/18}\le 2^{-20} e − r /18 ≤ 2 − 20 且 r r r 為奇數。取對數,r / 18 ≥ 20 ln 2 r/18\ge 20\ln 2 r /18 ≥ 20 ln 2 ,即 r ≥ 360 ln 2 r\ge 360\ln 2 r ≥ 360 ln 2 。由於 ln 2 ≈ 0.693147 \ln 2\approx 0.693147 ln 2 ≈ 0.693147 ,得 360 ln 2 ≈ 249.53 360\ln 2\approx 249.53 360 ln 2 ≈ 249.53 。整數 250 250 250 及更大者滿足不等式,但 250 250 250 是偶數,可能出現平局,因此最小的可接受奇數值是 r = 251 r=251 r = 251 。作為檢驗,251 / 18 ≈ 13.944 251/18\approx 13.944 251/18 ≈ 13.944 ,而 20 ln 2 ≈ 13.863 20\ln 2\approx 13.863 20 ln 2 ≈ 13.863 ,故 e − 251 / 18 < 2 − 20 e^{-251/18}\lt 2^{-20} e − 251/18 < 2 − 20 ,符合要求。相反,249 / 18 ≈ 13.833 < 13.863 249/18\approx 13.833\lt 13.863 249/18 ≈ 13.833 < 13.863 不滿足不等式。
該命題給出的上界可能與真實值相差甚遠。下一個例子計算小規模多數的精確錯誤,並與保證的界作比較。
例題 1.1.5
(小規模多數的精確錯誤與保證的界)
設單次運行在固定輸入上的錯誤概率恰為 1 / 4 1/4 1/4 。這符合有界公平位元模型:兩個新的公平位元有四個等可能結果,錯誤事件可以是結果 00 00 00 。固定有限個公平位元不可能產生恰為 1 / 3 1/3 1/3 的概率;BPP 定義中的 1 / 3 1/3 1/3 是上界,並不要求實際達到。對奇數 r r r ,獨立重複後的精確多數錯誤概率為
∑ k = ( r + 1 ) / 2 r ( r k ) ( 1 4 ) k ( 3 4 ) r − k = 1 4 r ∑ k = ( r + 1 ) / 2 r ( r k ) 3 r − k . \sum_{k=(r+1)/2}^{r}\binom rk\left(\frac14\right)^k\left(\frac34\right)^{r-k}=\frac1{4^r}\sum_{k=(r+1)/2}^{r}\binom rk 3^{\,r-k}. k = ( r + 1 ) /2 ∑ r ( k r ) ( 4 1 ) k ( 4 3 ) r − k = 4 r 1 k = ( r + 1 ) /2 ∑ r ( k r ) 3 r − k .
當 r = 1 r=1 r = 1 時,錯誤為 1 / 4 = 0.25 1/4=0.25 1/4 = 0.25 。
當 r = 3 r=3 r = 3 時,分子為 3 ⋅ 3 + 1 = 10 3\cdot3+1=10 3 ⋅ 3 + 1 = 10 ,所以錯誤為 10 / 64 = 5 / 32 = 0.15625 10/64=5/32=0.15625 10/64 = 5/32 = 0.15625 ,小於一般界 e − 1 / 6 ≈ 0.846 e^{-1/6}\approx0.846 e − 1/6 ≈ 0.846 。
當 r = 5 r=5 r = 5 時,分子為 10 ⋅ 9 + 5 ⋅ 3 + 1 = 106 10\cdot9+5\cdot3+1=106 10 ⋅ 9 + 5 ⋅ 3 + 1 = 106 ,所以錯誤為 106 / 1024 = 53 / 512 ≈ 0.104 106/1024=53/512\approx0.104 106/1024 = 53/512 ≈ 0.104 ,小於 e − 5 / 18 ≈ 0.757 e^{-5/18}\approx0.757 e − 5/18 ≈ 0.757 。
當 r = 7 r=7 r = 7 時,分子為 35 ⋅ 27 + 21 ⋅ 9 + 7 ⋅ 3 + 1 = 1156 35\cdot27+21\cdot9+7\cdot3+1=1156 35 ⋅ 27 + 21 ⋅ 9 + 7 ⋅ 3 + 1 = 1156 ,所以錯誤為 1156 / 16384 = 289 / 4096 ≈ 0.071 1156/16384=289/4096\approx0.071 1156/16384 = 289/4096 ≈ 0.071 ,小於 e − 7 / 18 ≈ 0.678 e^{-7/18}\approx0.678 e − 7/18 ≈ 0.678 。
這四個取值的精確錯誤依次下降。由於 1 / 4 ≤ 1 / 3 1/4\le1/3 1/4 ≤ 1/3 ,所引上界仍然適用,但有意保留較鬆的估計。它的價值在於:對任何奇數次重複,以及任意一組各自錯誤概率至多為 1 / 3 1/3 1/3 的獨立運行,都給出簡單的指數保證。精確的二項式計算要求各次概率相同,一般上界則不需要這項條件。
一個單側的例子
設某 RP 算法每次運行以至少 1 / 2 1/2 1/2 的概率接受一個「是」輸入。在 r r r 次獨立運行中,若任何一次運行接受便接受,則漏掉該輸入的概率至多為 ( 1 / 2 ) r (1/2)^r ( 1/2 ) r 。對於「否」輸入,每次運行都以概率 1 1 1 拒絕,因此合併後的算法永不接受「否」輸入。乘積界需要獨立性;重複使用同一隨機種子未必能改善錯誤。
聲稱某算法在某個分佈下對 99% 的輸入是正確的,這是平均情況的主張。BPP 則要求其成功界分別對每個輸入成立,而概率是針對全新的內部隨機位元。一個算法可以平均表現良好,卻在某個特定輸入上持續失敗。
上面的計算並未用到常數 1 / 2 1/2 1/2 或某個特定算法的任何特殊性質,因此可以一般地陳述並證明。
設 M M M 為運行時間為 T ( n ) T(n) T ( n ) 的隨機化算法,使得 L L L 之外的每個輸入都以概率 1 1 1 被拒絕,且對某個 ε ∈ [ 0 , 1 ) \varepsilon\in[0,1) ε ∈ [ 0 , 1 ) ,L L L 中的每個輸入都以至少 1 − ε 1-\varepsilon 1 − ε 的概率被接受。設 M ( r ) M^{(r)} M ( r ) 在 r r r 個獨立隨機字串上運行 M M M ,並且恰在至少有一次運行接受時接受。則 M ( r ) M^{(r)} M ( r ) 以概率 1 1 1 拒絕 L L L 之外的每個輸入,並以至少 1 − ε r 1-\varepsilon^r 1 − ε r 的概率接受 L L L 中的每個輸入。其運行時間為 O ( r T ( n ) ) O(r\,T(n)) O ( r T ( n )) 加上簿記的開銷。
固定輸入 x x x ,設 ρ 1 , … , ρ r \rho_1,\dots,\rho_r ρ 1 , … , ρ r 為獨立的隨機字串。若 x ∉ L x\notin L x ∈ / L ,則每次運行對每個字串都拒絕,或至少以概率 1 1 1 拒絕,故所有 r r r 次運行以概率 1 1 1 全部拒絕,合併後的算法拒絕。若 x ∈ L x\in L x ∈ L ,合併後的算法恰在所有運行都拒絕時才拒絕。由獨立性,此事件的概率等於各次拒絕概率之積,每個至多為 ε \varepsilon ε ,故至多為 ε r \varepsilon^r ε r 。運行時間是 r r r 次運行時間之和,再加上每次運行用以記錄是否出現接受的常數開銷。
取 ε = 1 / 2 \varepsilon=1/2 ε = 1/2 以及某個多項式 q q q 的 r = q ( n ) r=q(n) r = q ( n ) ,假陰性概率至多為 2 − q ( n ) 2^{-q(n)} 2 − q ( n ) 。此外,ε \varepsilon ε 不必是 1 / 2 1/2 1/2 :任何至多為 1 − 1 / p o l y ( n ) 1-1/\mathrm{poly}(n) 1 − 1/ poly ( n ) 的單側錯誤界,都可以用多項式次數的重複化為指數級小的錯誤,因為當 p ≥ 1 p\ge1 p ≥ 1 時 ( 1 − 1 / p ) p q ≤ e − q (1-1/p)^{pq}\le e^{-q} ( 1 − 1/ p ) pq ≤ e − q ;下面的練習處理常數界 ε = 2 / 3 \varepsilon=2/3 ε = 2/3 的情形。
P、RP 與 BPP 之間的包含關係
討論錯誤保證時所述的包含關係現在給出證明,並附帶證明與 N P \mathrm{NP} NP 的另一個關係。回顧:當存在多項式時間確定性驗證者 V V V 與多項式 q q q ,使得 x ∈ L x\in L x ∈ L 當且僅當存在某個證書 w w w (∣ w ∣ = q ( ∣ x ∣ ) |w|=q(|x|) ∣ w ∣ = q ( ∣ x ∣ ) )令 V ( x , w ) V(x,w) V ( x , w ) 接受時,L ∈ N P L\in\mathrm{NP} L ∈ NP 。
P ⊆ R P ⊆ B P P \mathrm P\subseteq\mathrm{RP}\subseteq\mathrm{BPP} P ⊆ RP ⊆ BPP 且 R P ⊆ N P \mathrm{RP}\subseteq\mathrm{NP} RP ⊆ NP 。
P ⊆ R P \mathrm P\subseteq\mathrm{RP} P ⊆ RP :對 L L L 的確定性多項式時間判定器,在忽略其隨機位元的情況下運行,以概率 1 ≥ 1 / 2 1\ge 1/2 1 ≥ 1/2 接受每個成員,並以概率 1 1 1 拒絕每個非成員。
R P ⊆ B P P \mathrm{RP}\subseteq\mathrm{BPP} RP ⊆ BPP :設 M M M 見證 L ∈ R P L\in\mathrm{RP} L ∈ RP ,並考慮這樣的算法:在獨立字串上運行 M M M 兩次,若任一次接受便接受。由單側放大命題(ε = 1 / 2 \varepsilon=1/2 ε = 1/2 ,r = 2 r=2 r = 2 ),它以概率 1 1 1 拒絕每個非成員,並以至少 1 − 1 / 4 = 3 / 4 ≥ 2 / 3 1-1/4=3/4\ge 2/3 1 − 1/4 = 3/4 ≥ 2/3 的概率接受每個成員。因此它在每個輸入上以至少 2 / 3 2/3 2/3 的概率答對,且在多項式時間內運行。
R P ⊆ N P \mathrm{RP}\subseteq\mathrm{NP} RP ⊆ NP :設 M M M 至多使用 p ( n ) p(n) p ( n ) 個隨機位元。定義驗證者 V ( x , w ) V(x,w) V ( x , w ) :它在 x x x 上模擬 M M M ,以證書 w ∈ { 0 , 1 } p ( ∣ x ∣ ) w\in\{0,1\}^{p(|x|)} w ∈ { 0 , 1 } p ( ∣ x ∣ ) 作為隨機字串,並恰在 M M M 接受時接受。這是一個多項式時間確定性計算。若 x ∈ L x\in L x ∈ L ,接受概率為正,故在有限多個隨機字串中至少有一個使 M M M 接受,從而存在良好的證書。若 x ∉ L x\notin L x ∈ / L ,沒有任何字串使 M M M 接受,故沒有證書被接受。
證明透視
每個包含關係用到甚麼 每個包含關係用到定義的不同部分。P ⊆ R P \mathrm P\subseteq\mathrm{RP} P ⊆ RP 只需要確定性算法可以忽略它的隨機位元。R P ⊆ B P P \mathrm{RP}\subseteq\mathrm{BPP} RP ⊆ BPP 需要放大:單次運行的假陰性概率 1 / 2 1/2 1/2 對 BPP 的門檻太大,所以把兩次獨立運行用 OR 合併,得到 3 / 4 ≥ 2 / 3 3/4\ge2/3 3/4 ≥ 2/3 ,而非成員仍以概率 1 1 1 被拒絕。R P ⊆ N P \mathrm{RP}\subseteq\mathrm{NP} RP ⊆ NP 正是單側錯誤不可或缺之處:正是零假陽性的性質,把一個良好的隨機字串變成可驗證的證書。練習會問對 BPP 而言哪裏行不通。
這些論證都沒有說明任何一個包含關係是嚴格的。這些類別是否重合的問題,並未被本單元中的任何內容解決。
練習與解答
快速檢查
(需要多少次獨立的 RP 重複,才足以使假陰性概率至多為 1 / 32 1/32 1/32 ?)
解答 · 答案 五次重複已足夠,因為 ( 1 / 2 ) 5 = 1 / 32 (1/2)^5=1/32 ( 1/2 ) 5 = 1/32 。
快速檢查
(為甚麼若所有重複都使用完全相同的隨機位元,多數表決就不能保證降低錯誤?)
解答 · 答案 此時每次重複的輸出可能都相同。多數返回的答案與第一次運行相同,因此其錯誤概率可能毫無改變;獨立試驗的界並不適用。
快速檢查
(某隨機化算法在某固定輸入上恰以 1 / 4 1/4 1/4 的概率出錯。計算 3 3 3 次獨立運行的多數之精確錯誤概率。)
解答 · 答案 三次的多數在至少兩次運行出錯時為錯。恰好兩次出錯的概率是 3 ⋅ ( 1 / 4 ) 2 ⋅ ( 3 / 4 ) = 9 / 64 3\cdot(1/4)^2\cdot(3/4)=9/64 3 ⋅ ( 1/4 ) 2 ⋅ ( 3/4 ) = 9/64 ,三次都出錯的概率是 ( 1 / 4 ) 3 = 1 / 64 (1/4)^3=1/64 ( 1/4 ) 3 = 1/64 。總和為 10 / 64 = 5 / 32 = 0.15625 10/64=5/32=0.15625 10/64 = 5/32 = 0.15625 ,小於單次運行的錯誤 1 / 4 1/4 1/4 。
快速檢查
(利用成功概率為 2 / 3 2/3 2/3 時的指數界,求一個奇數的重複次數,使其保證錯誤至多為 10 − 6 10^{-6} 1 0 − 6 。)
解答 · 答案 我們需要 e − r / 18 ≤ 10 − 6 e^{-r/18}\le 10^{-6} e − r /18 ≤ 1 0 − 6 ,故 r ≥ 18 ln ( 10 6 ) = 18 ⋅ 6 ln 10 ≈ 18 ⋅ 13.8155 ≈ 248.68 r\ge 18\ln(10^6)=18\cdot 6\ln 10\approx 18\cdot 13.8155\approx 248.68 r ≥ 18 ln ( 1 0 6 ) = 18 ⋅ 6 ln 10 ≈ 18 ⋅ 13.8155 ≈ 248.68 。不小於 248.68 248.68 248.68 的最小奇整數為 r = 249 r=249 r = 249 。作為檢驗,249 / 18 ≈ 13.833 ≥ 13.8155 249/18\approx 13.833\ge 13.8155 249/18 ≈ 13.833 ≥ 13.8155 ,故 e − 249 / 18 ≤ 10 − 6 e^{-249/18}\le 10^{-6} e − 249/18 ≤ 1 0 − 6 。
快速檢查
(某算法永不接受非成員,並以至少 1 / 3 1/3 1/3 的概率接受每個成員。需要多少次獨立重複(任一次運行接受即接受),才能保證假陰性概率至多為 1 / 100 1/100 1/100 ?)
取 ε = 2 / 3 \varepsilon=2/3 ε = 2/3 。
解答 · 答案 應用單側放大,取 ε = 2 / 3 \varepsilon=2/3 ε = 2/3 :需要 ( 2 / 3 ) r ≤ 1 / 100 (2/3)^r\le 1/100 ( 2/3 ) r ≤ 1/100 。由於 ( 2 / 3 ) 11 = 2048 / 177147 ≈ 0.01156 > 0.01 (2/3)^{11}=2048/177147\approx 0.01156\gt 0.01 ( 2/3 ) 11 = 2048/177147 ≈ 0.01156 > 0.01 而 ( 2 / 3 ) 12 = 4096 / 531441 ≈ 0.00771 ≤ 0.01 (2/3)^{12}=4096/531441\approx 0.00771\le 0.01 ( 2/3 ) 12 = 4096/531441 ≈ 0.00771 ≤ 0.01 ,最小的充分次數是 r = 12 r=12 r = 12 。等價地,r ≥ ln 100 / ln ( 3 / 2 ) ≈ 4.605 / 0.4055 ≈ 11.36 r\ge\ln 100/\ln(3/2)\approx 4.605/0.4055\approx 11.36 r ≥ ln 100/ ln ( 3/2 ) ≈ 4.605/0.4055 ≈ 11.36 。
快速檢查
(某次運行在某固定輸入上以至少 0.6 0.6 0.6 的概率正確。利用優勢命題,求一個奇數的運行次數,使多數以至少 2 / 3 2/3 2/3 的概率正確。)
解答 · 答案 這裏 δ = 0.1 \delta=0.1 δ = 0.1 ,故多數出錯的概率至多為 exp ( − 2 ⋅ 0.01 ⋅ r ) = e − r / 50 \exp(-2\cdot 0.01\cdot r)=e^{-r/50} exp ( − 2 ⋅ 0.01 ⋅ r ) = e − r /50 。我們需要 e − r / 50 ≤ 1 / 3 e^{-r/50}\le 1/3 e − r /50 ≤ 1/3 ,即 r ≥ 50 ln 3 ≈ 50 ⋅ 1.0986 ≈ 54.93 r\ge 50\ln 3\approx 50\cdot 1.0986\approx 54.93 r ≥ 50 ln 3 ≈ 50 ⋅ 1.0986 ≈ 54.93 。不小於 54.93 54.93 54.93 的最小奇整數為 r = 55 r=55 r = 55 ,而且確實 e − 1.1 ≈ 0.3329 ≤ 1 / 3 e^{-1.1}\approx 0.3329\le 1/3 e − 1.1 ≈ 0.3329 ≤ 1/3 。這是由上界得到的充分次數,未必是達到目標的最小次數。
快速檢查
(R P ⊆ N P \mathrm{RP}\subseteq\mathrm{NP} RP ⊆ NP 的證明把隨機字串視為證書。解釋為何同樣的想法不能證明 B P P ⊆ N P \mathrm{BPP}\subseteq\mathrm{NP} BPP ⊆ NP 。)
解答 · 答案 對於 BPP 語言,成員至少有 2 / 3 2/3 2/3 比例的接受隨機字串,因此存在接受字串。但非成員仍可能有高達 1 / 3 1/3 1/3 比例的接受字串,因為 BPP 允許假陽性。一個在模擬於證書上接受時便接受的驗證者,會因此接受某些非成員,這違反了 NP 對非成員不得有任何證書被接受的要求。RP 的零假陽性性質,恰恰使該模擬成為可靠的驗證者。
續篇《方差界與隨機恆等檢驗》繼續討論方差論證與多項式恆等檢驗。