Computational-Complexity-Theory
統一和非統一的 PPT
讀報的時候
- 2020 - Dana Dachman-Soled 和 Ilan Komargodski 以及 Rafael Pass的有界多項式深度篡改的不可延展程式碼
我偶然發現有必要說明作者是假設統一的攻擊者還是不統一的攻擊者。據我所知，非統一的PPT基本上是一系列PPT，所以 $ \mathcal{A}={\mathcal{A}_1,\mathcal{A}_2,\dots,\mathcal{A}n} $ , 並在輸入 $ x $ 大小的 $ |x| = \lambda $ , $ \mathcal{A}\lambda $ 叫做。為什麼這個模型比制服模型“強”？無法廣告攻擊者 $ \mathcal{A} $ 只是將所有其他攻擊者嵌入到自己的描述中並呼叫合適的攻擊者？是否存在我們知道如何在統一模型中解決但在非統一模型中不知道（如果沒有更弱的保證）的問題？
考慮所有圖靈機的一元列舉，例如一台機器 $ M $ 表示為 $ 1^{\lambda_M} $ 對於一些唯一的整數 $ \lambda_M $ . 即使在這種“稀疏”表示中，停止問題也是無法計算的。但它是非均勻可計算的，因為每個圖靈機 $ M $ 要麼停止，要麼不停止，我們可以“硬編碼”決定這個到每台圖靈機 $ A_{\lambda_M} $ .
如果我們可以“統一生成” $ A_i $ 的，意義有效地從單獨的描述中生成它們 $ i $ ，你是對的。在上面的例子中，你不能，因為你不知道每個圖靈機是否 $ M $ 停止。