為什麼互動式證明中的證明者在計算空間的指數時間內執行？
我目前正在嘗試了解可驗證計算以及過去方法的優缺點。
特別是，我一直在觀看以下YouTube 影片，其中討論了互動式證明作為驗證計算知識的一種方式。在時間 11:55 出現的幻燈片上，它提到證明者在計算空間中需要指數時間。誰能解釋這是怎麼回事？
我也對每一個確定性計算都有一個互動式證明的說法感到困惑。
我試過閱讀下面的論文，但似乎無法找到對這些結果的明確解釋。任何幫助將非常感激！
參考：
隆德，卡斯滕等人。“互動式證明系統的代數方法”。ACM 雜誌 (JACM) 39.4 (1992): 859-868。
沙米爾，阿迪。“IP = pspace。” ACM 雜誌 (JACM) 39.4 (1992): 869-877。
可驗證計算的全部意義在於允許驗證者驗證計算是否正確執行，而無需自己執行計算。因為像往常一樣，我們將“多項式時間”與“高效計算”聯繫起來，如果計算需要多時間，那麼使用可驗證計算就沒有意義，因為驗證者也可以自己執行計算。
在一般的證明系統中，如果驗證者可以自己確定所討論陳述的真實性，則根本不需要證明者。
以下是對您第一個問題的回答。
這是我發現很難用通常的互動式證明展示來掌握的一件事，所以我認為這是一個很好的問題。
互動式證明有兩個總體目標。
- 首先，驗證者應該只需要進行廉價的計算（高效，即多項式時間）來確信一個陳述是正確的。
- 其次，無論他願意付出多少計算努力，證明者都不應該能夠始終如一地說服驗證者接受一個非事實。（這就是給我們一個“證明”的原因。）
大多數學生沒有想到的是，雖然驗證者必須是高效的，但並不要求證明者應該是高效的。因此，在範例中，效率不高的證明者往往會不時出現。
為什麼我們不要求證明者高效？我不是這方面的專家，但我相信它為我們提供了更豐富、更普遍的理論。從理論的角度來看，這是一個完全有效的觀點。
然而，當互動式證明的理論與密碼學發生衝突時，這對學生來說就變得很尷尬，因為在密碼學中，一個非高效的證明者似乎沒有意義。顯然，允許作弊證明者無效是有一定價值的（類似於資訊論安全性），但在密碼學中，我們實際上打算（至少在理論上）執行一個非作弊證明者，這意味著它必須是高效的。因此，互動式證明的通常定義在密碼學中沒有直覺意義。
總結一下：互動式證明的理論不是密碼學。該理論並不完全適用於密碼學。但是，它對於密碼學至關重要。