固定的是輸入,隨機的是算法的擲幣
隨機算法對同一輸入可能給出不同答案。正確性陳述必須交代:哪種答案可能錯、錯誤概率多大,以及概率取自哪裏。這些細節決定怎樣重複才安全。「只要有一次接受就接受」很適合某些單邊錯誤測試,卻可以令雙邊錯誤測試更不可靠。
我們研究以語言 表示的決定問題; 就是肯定實例。本節的每個錯誤概率都是:先固定任意輸入,再對算法的公平隨機位元取概率。我們沒有假設輸入服從某種分佈。
三種不同的正確性保證
定義 7.1.1
(多項式時間隨機決定算法)
算法 接收輸入 與隨機帶 。對每個長度為 的輸入及每條隨機帶,執行時間都有同一個多項式上界,故所用隨機位元亦至多有多項式個 。把未用位元補齊,令同一輸入長度的帶等長,再均勻選取。
下表是算法辨認 時的保證:
| 類別 | 若 | 若 |
|---|---|---|
| RP | 接受概率至少 | 絕不接受 |
| coRP | 必定接受 | 接受概率至多 |
| BPP | 接受概率至少 | 接受概率至多 |
若存在符合某行保證的算法,語言便屬於該類別。這裏的時間界是對隨機帶取最壞情形,不只是期望時間界。
RP 的接受答案可以確定輸入是肯定實例;拒絕則可能只是本次隨機試驗錯過見證。coRP 相反,拒絕可以確定是否定實例。BPP 的兩種答案都可能錯。這些條件不容許算法只在大部分輸入上正確:每個個別輸入都必須符合所屬行的界。
表中的常數是方便的基準。放大真正需要的是失敗概率與相關門檻之間留有合適差距。以下直接證明這些常數下的界,不把任何重複程序都當作自動有效。
RP 放大要保留確定正確的答案
用獨立的新隨機帶執行 RP 算法 次,至少一次接受就接受。否定實例每次都拒絕,所以仍不會錯誤接受。固定肯定實例,設單次拒絕概率為 ;重複程序出錯,必須全部 次都拒絕。由獨立性,
要把錯誤降至 ,取 即可。時間與隨機位元用量都增加 倍。
例題 7.1.2
(具有單邊錯誤的小型抽樣測試)
輸入有四個位元,問題是是否至少一位為 1。一次試驗獨立且均勻地有放回抽取三個索引;只要抽到 1 就接受。全零輸入不可能被接受。有至少一位 1 時,最壞情況恰有一位 1,因此拒絕概率為
所以這個固定大小例子符合 RP 的錯誤保證。對 0010,接受概率為 。兩次獨立的三抽樣試驗用 OR 合併,漏掉該 1 的概率為 。
這是用來看清保證的例子,沒有宣稱加速:直接讀完四位,就可以確定性地解決這個小問題。
coRP 用對偶規則:全部 次都接受才接受。肯定實例仍必定接受,否定實例的錯誤接受概率則至多 。
兩次重複已足以把任一單邊類別放進 BPP,因唯一可能的錯誤至多 。確定性多項式時間算法忽略隨機帶,就同時符合兩種單邊保證。把 BPP 算法的輸出取反也保留錯誤界,因此 BPP 對補集封閉。
反例模式
OR 也可以放大錯誤答案
假設 BPP 算法在某個否定實例上,以 概率接受。若獨立執行 次後只要一次接受就接受,錯誤接受概率變成 ,並趨近 1;三次時已是 。
同樣,要求全部接受會破壞肯定實例的保證。若單次接受概率是 ,合併後便是 ,趨近 0。
合併規則必須配合錯誤保證。只說「重複執行」,還未指定正確的放大算法。
多數決處理雙邊有界錯誤
BPP 可獨立重複奇數次 ,回傳多數答案。固定任意輸入 ;第 次錯時令 ,否則為 0。每次錯誤概率至多 ,而新隨機帶彼此獨立,故 亦獨立。多數答案錯誤,至少要有 次出錯。
定理 7.1.3
(初等的指數多數決錯誤界)
若 為奇數,獨立重複並採多數決,則對每個固定輸入,
因 ,此上界隨 指數下降。
證明
(用非負指數量偵測大量錯誤)
對非負隨機變量 與 ,有 :在事件 上,對期望的貢獻至少是 乘該事件概率。這就是 Markov 不等式。
記 。多數錯誤蘊含 ,因此 。若 ,則 。用獨立性可得
把期望拆成乘積的等號,正是使用獨立性的地方。此證明不需要算法在不同輸入上的行為彼此獨立。
證明透視
證明在哪裏用到各個假設
證明有三個運作部分。底數 使 容易計算,並把 轉成 ;換另一個底數會得到另一個常數。錯誤假設 只通過 進入,所以證明不需要 的精確值。獨立性恰好用一次,就是把 拆成乘積;Markov 不等式和逐個因子的上界都不需要它。最後,對錯誤概率 ,最終指數的底是 ,恰在 時小於 ,所以這個初等計算用到 與該門檻之間的距離。
取不小於下式的奇數 ,即可令上界至多為 :
重複次數為 。特別地,正多項式 所指定的錯誤 ,可以由 BPP 算法在多項式時間達到。要求任意微小錯誤並非免費:若 對輸入長度已是指數,此放大程序未必仍是多項式時間。
例題 7.1.4
(要運行多少次才能令錯誤至多 ?)
設要從 BPP 算法得到至多 的錯誤。上界要求 ,所以最小的奇數取值是 。為看出它有多鬆,設每次運行的錯誤概率為 ,取 。精確的多數決錯誤為 ,而上界給出 。上界有效但偏保守:它保證的是指數級的下降速率,不是最少的重複次數。
上界不等於實際錯誤
例題 7.1.5
(三次運行的精確多數決錯誤)
為這項計算,假設固定輸入上三次獨立執行的錯誤概率都恰為 。這個概率可由有限均勻公平位元帶產生,恰為 則不行;BPP 定義把 當上界,沒有要求能取等號。錯誤次數分佈如下:
| 錯誤次數 | 概率 | 多數答案錯誤? |
|---|---|---|
| 0 | 否 | |
| 1 | 否 | |
| 2 | 是 | |
| 3 | 是 |
實際多數決錯誤為 。前述一般指數界對少量試驗刻意較鬆;它證明統一的下降速率,並非精確二項尾概率。
反例模式
複製隨機帶不會產生新證據
斷言:三次各以概率 出錯的運行,多數決錯誤永遠是 。假設某固定輸入上,基本算法恰在四分之一隨機帶上出錯,三次執行都使用同一條帶。輸入與帶完全決定計算,三個答案必然相同,所以多數決恰在單次出錯的那些帶上出錯。錯誤保持 ,不是 。各次單獨都符合錯誤概率,卻因相關而令多數決界證明中的乘積步驟失效。修正:各次運行使用新而獨立的隨機帶;獨立性是放大定理的假設,不只是實現上的外觀選擇。
同一輸入長度的一條好隨機帶
BPP 保證先固定 ,再對 取概率;它沒有說某條抽到的帶同時適用於全部輸入。不同輸入的壞帶可能不同。不過,先放大再用有限聯集界,就能得到有用的存在性結論。
定理 7.1.6
(一條多項式長度的帶可以處理所有長度 n 的輸入)
設 。對每個輸入長度 ,先把每輸入錯誤放大至至多 。對此放大算法,存在同一條隨機帶 ,使全部 個長度為 的二進制輸入都回答正確。
證明
(用聯集界一次計算所有輸入)
固定此長度,把放大算法的帶補至共同多項式長度 。對每個 ,令 是均勻所選帶使算法在 上出錯的事件。每事件概率至多 ,所以
聯集界不需要這些事件獨立。至少以 概率,一條帶不屬於任何壞事件,因此至少存在一條好帶。所需放大只用 次重複,所以 仍是多項式。
概念視角組合
輸入與隨機帶的表格
作一張表格:長度為 的每個輸入佔一行,每條隨機帶佔一列,算法出錯的格子加上標記。每一行中帶標記的格子至多佔 ,所以含有任何標記的列至多佔 。因此至少有一半的列沒有標記,而每個沒有標記的列,就是對所有輸入同時正確的一條隨機帶。
這給出非均勻結論。
定義 7.1.7
()
語言 屬於 ,是指存在多項式 、只依賴輸入長度 且長度為 的建議字串 ,以及確定性多項式時間機器 ,使得 當且僅當 接受。
推論 7.1.8
(BPP 包含於 P/poly)
。
證明
(建議就是那條好隨機帶)
設 。對每個長度 ,取上一個定理中放大算法的好隨機帶 作為建議 。確定性多項式時間機器以這條固定的帶模擬放大算法處理 。由 的選取,長度為 的每個輸入都答對,所以 。
常見錯誤
(建議不等於去隨機化)
量詞非常重要:每個長度都存在合適建議。證明沒有給出均勻多項式時間程序來找這些建議,因此沒有證明 ,也沒有說可在所有輸入長度重用同一條常數帶。建議的存在性與可執行的均勻去隨機化算法,是不同結論。
附解答練習
快速檢查
(獨立抽樣與重用抽樣結果)
對四位測試輸入 0010,計算兩次獨立三抽樣試驗用 OR 合併的失敗概率。若第二次重用第一次的三個索引,結果如何?
解答 · 答案
單次失敗為 ;獨立兩次同時失敗為 。重用索引會看到完全相同位元,所以合併失敗仍為 。OR 符合單邊保證,但把失敗概率相乘仍需要獨立。
快速檢查
(計算五次多數決錯誤)
固定輸入,假設五次獨立執行的錯誤概率都恰為 。求精確多數決錯誤。若輸入是否定實例,改用 OR 的錯誤接受概率是多少?
解答 · 答案
有三、四或五次錯誤時,多數答案錯誤:
否定實例上,每次錯誤就是接受。OR 只有全部五次都拒絕才不錯誤接受,所以錯誤為 。多數決改善雙邊錯誤,此 OR 規則卻令它增加。
快速檢查
(對全部十位輸入作同時保證)
假設共同長度的隨機帶,對每個十位輸入的錯誤都至多 。求一條帶至少在某個十位輸入出錯的概率上界。不同輸入的事件必須獨立嗎?好帶存在仍沒有提供甚麼?
解答 · 答案
共有 個輸入。由聯集界,至少一輸入出錯的概率至多 ,故至少以 概率,帶對全部十位輸入正確,好帶必然存在。不需要跨輸入獨立。存在性證明沒有提供對每個長度均勻且有效地找好帶的算法;均勻去隨機化主張所欠的正是此步。
快速檢查
(平均錯誤小是另一種保證)
設 是空語言。對長度 ,某確定性算法只接受 ,其餘全部拒絕。均勻隨機長度 n 輸入下的錯誤為 。它符合空語言的 BPP 保證嗎?
解答 · 答案
不符合。固定否定實例 上,它以概率 1 接受。輸入分佈下平均錯誤小,不能修補逐輸入保證的違反。空語言本身當然屬於 P 與 BPP:永遠拒絕就正確辨認它。失敗的是這個提議的算法,而非該語言的類別歸屬。