證明使用了特定算法
我正在尋找一種方法的存在（或不存在的證明）來證明（具有任意確定性）特定輸出是應用於特定輸入的特定算法的結果。 $$ f(x) = y $$ 我如何通過知道上面的方程的所有成分但沒有實際應用函式來證明上面的方程成立？
這類似於零知識證明，但可以很容易地在區塊鏈中使用以嵌入人工智慧算法。
給定輸入（相關）或算法（線性）的一些限制，您知道任何這樣的方法嗎？
我正在尋找一種方法的存在（或不存在的證明）來證明（具有任意確定性）特定輸出是應用於特定輸入的特定算法的結果。
如果“特定算法”是指“任何算法”，那麼絕對不存在這樣的方法，因為在確定算法是否為特定輸入提供特定輸出之前，您首先必須確定該算法是否甚至在該特定輸入上停止，並且眾所周知，停止問題是不可判定的。請注意，即使取消對不實際執行算法的限制也不會讓您擺脫這種情況。
如果“特定算法”是指“我現在正在考慮的特定算法”，那麼一般來說，正如評論中所討論的那樣，如果你有一個輸入和一個輸出，那麼就有無數種不同的算法可以構造從特定輸入產生特定輸出的函式，因此僅通過檢查這兩個值是不可能區分它們的。
另一方面，如果您只想測試給定算法是否會針對給定輸入給出特定輸出，而不管某些不同的函式是否也可能給出相同的輸出，那麼至少存在一些相關情況這不是——或者不應該——是可能的。例如，任何分組密碼都應該輸出不洩露任何關於密鑰或明文的可用資訊的密文。即使您擁有密鑰和明文，如果您可以知道給定的密文將由它們生成而無需實際執行加密（或解密）功能，那麼該功能就會被破壞。
一般來說，如果你有所有的輸入、所有的輸出和算法的全部知識，那麼這裡的“零知識證明”意味著什麼就不清楚了，因為你顯然擁有執行算法所需的所有知識你自己。有一個證書值的概念，它可以證明一個昂貴的算法 - 例如，您可以通過簡單地提供正確的指數來證明您解決了給定的離散對數，因此任何人都可以輕鬆驗證它而無需麻煩解決它本身 - 但這完全取決於所討論的算法。
如果你允許這種陳述的證明者和驗證者之間進行互動，那麼這開始看起來像可驗證計算的設置。參見例如這個 Wikipedia 條目或Goldwasser、Kalai 和 Rothblum 的這篇論文。目的是讓證明者說服計算能力弱得多的驗證者它確實適用 $ f(\cdot) $ 至 $ x $ 並獲得 $ y $ 通過互動證明。這種證明的健全性需要證明者實際進行計算才能說服驗證者。如果你想讓整個事情變得非互動式，你可以使用Fiat-Shamir heuristic。
回到你的問題，
我如何通過知道上面的方程的所有成分但沒有實際應用函式來證明上面的方程成立？
驗證者將確信該等式在不應用該函式的情況下成立（但證明者需要應用該函式）。
我假設 $ f(\cdot) $ 是有效可計算的（即在 $ \mathsf P $ )，因為如果是這種情況，那麼PCP 定理應該確保任何這樣的互動證明都存在 $ f $ .