Provable-Security
通過還原澄清證明
如果我使用給定的對手 A 作為 A’ 的子程序通過減少來執行證明。我怎麼知道使用可以解決給定困難子問題的對手 A 是用於解決 A’ 解決的更大問題的最有效子程序？
提前致謝。
在減少你有兩個問題A和B，A $ \leq $ B 表示如果您可以解決問題 B，那麼您就可以解決問題 A，現在在大多數簡化中，除非您添加更多步驟，否則您構造的 A 求解器的有效水平與 B 相同。所以這意味著你無法知道它是否最有效，它可能是也可能不是。
你沒有，除非你指定 $ A $ 是最有效的。
但是為了可證明的安全性，您不想建構任何真實的東西，並且不關心除了最高級別（通常是多時間算法與否）之外的效率。您想表明，在硬度假設下，這樣一個真正的求解器是不存在的。這通常是在反證法中完成的。