驗證者是什麼意思是“ppt”？為什麼我們需要verifier is ppt in Interactive Proof？

我一直在研究零知識證明。我發現互動式證明的定義說驗證者是 ppt。我只在PP (Complexity) Wikipedia中發現ppt：

多項式綁定和機率的圖靈機被描述為PPT，它代表機率多項式時間機器。

$$ 2 $$圖靈機的這種表徵不需要有界錯誤機率。因此，PP 是包含錯誤機率小於 1/2的PPT機器可解決的所有問題的複雜度類。

對PPT還是很困惑，PPT的全稱是什麼？我們是否需要驗證者是互動式證明的 PPT？

資源來自：零知識證明 CS276：密碼學，加州大學伯克利分校

PPT是機率多項式時間算法。

確定性驗證器將始終為任何輸入產生相同的輸出/回复。

讓我們看一個互動序列。

證明者發送 $ p_1 $ .

驗證者回复 $ f(p_1) = v_1 $

證明者回复 $ g(v_1) = p_2 $

功能 $ f $ 驗證者使用的是確定性的。即對於特定的輸入，它總是以相同的回復進行回复。

在機率驗證器中， $ f $ 也有隨機化作為輸入。IE $ g $ 需要 2 個輸入 $ f(v_i, r) $ 在哪裡 $ r $ 是一個隨機值。因此 $ f $ 不是確定性的，驗證者是機率驗證者。而如果 $ f $ 在多項式時間內執行，驗證器是機率多項式時間（PPT）驗證器。

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