互動式證明：為什麼δ<13δ<13delta lt frac 13為了健全性和完整性？

來自互動式證明的文本

$ x \in {0,1}^n $ 是輸入

$ V $ 是驗證者

$ P $ 是證明者

$ r $ 是 $ V $ 的內部隨機性

$ P $ 提供一個值 $ y $ 據稱等於 $ f(x) $

1. （完整性）對於每個 $ x \in {0,1}^n $

$ Pr[out(V, x, r, P) = 1] \ge 1 - \delta_c $

2. （健全）對於每個 $ x \in {0,1}^n $ 以及每個確定性證明者策略 $ P’ $ ， 如果 $ P’ $ 發送一個值 $ y \ne f(x) $ 在協議開始時，然後

$ Pr[out(V,x,r;P’) = 1] \le \delta_s $

互動式證明系統是有效的，如果 $ \delta_c, \delta_s \le \frac 13 $

有什麼意義 $ \frac 13 $ 這裡？為什麼有 $ \frac 13 $ 被選為什麼 2 $ \delta $ s 必須小於？我的意思是為什麼不 $ \frac 14 $ 或者 $ \frac 12 $ 或者是其他東西？

這是任意的。只要類的定義不變 $ \delta $ s 足夠遠離 $ 1/2 $ ，其中“充分”是指一個不可忽略的值 $ n $ ，因為它們可以被放大（例如通過平行重複）以壓倒性地接近 $ 1 $ . $ 1/3 $ 滿足這個標準。參見維基百科關於類的文章中定義後的討論 $ \mathbf{BPP} $ .

引用自：https://crypto.stackexchange.com/questions/101977