沒有快速路徑和快速證明的函式
當一個函式被迭代並且每次將先前的結果用作下一次迭代的輸入（回饋）時，並行計算的好處有限，是否存在這樣的函式：
- 需要多項式時間來獲得 N 次迭代的結果
- 有第 N 個結果，可以在恆定時間內驗證為給定起始值的第 N 個結果
假設 Alice 迭代函式：
Makwa 的問題：起初 Bob 必須使用並丟棄 p 和 q。
LCS35 的問題：起初 Bob 必須建構這個謎題。
但我需要一個函式，以便 Alice 可以選擇任意數字或數據開始迭代，而不是 Bob 準備的東西。只有當 Alice 完成 N 次迭代後 Bob 才會加入並驗證。
即使誠實的證明者不使用迭代，以下段落也適用。
嚴格來說，在恆定時間內只能讀取輸入的恆定大小部分
，因此總是可以在恆定時間內找到合適的結果。
對於一個確定性驗證器，最多對 由 M個 w 位字組成的所謂結果進行 k 次探測，可以找到一個合適的結果 2
$ \hspace{.02 in} $ 在 $ \hspace{.02 in}\cdot $ 驗證者的k個並行模擬，每個只使用 $ (\hspace{.02 in}2\hspace{-0.05 in}\cdot \hspace{-0.04 in}k)\hspace{-0.04 in}+\hspace{.02 in} $ O (1) 成本的話。
相反，如果驗證者是機率性的，那麼要麼 $ \binom{M}{\hspace{.02 in}k\cdot \hspace{.02 in}(1+\hspace{.03 in}\Omega(1))\hspace{-0.03 in}} $ $ \cdot $ 2 $ \hspace{.02 in} $ 在 $ \hspace{.02 in}\cdot $ ķ $ \cdot $ (1+ $ \hspace{.03 in} $ Ω (1)) 並行
模擬就足夠了，或者對手可以非常有效地從實際結果
變為使驗證者的接受機率介於 Ω(1) 和 1- 之間的 $ \hspace{.02 in} $ Ω(1)。 但是，很可能通過簡單地接受“對手……介於……之間”來 使用機率詞 RAM
驗證器 來實現您所詢問的內容 。與高效驗證者接近的 PCP 會做一些類似的事情。