Provable-Security
PPT與NP問題
安全性的通用定義（對於某些密碼原語）是針對任何 PPT 對手（在多項式時間內執行的任何機率算法）的安全性。同時，我們假設這個原語中的潛在問題是 NP 問題（一組可以通過理論上的非確定性圖靈機在多項式時間內解決的決策問題，link）。
PPT算法是否與非確定性多項式相同？如果是，那麼我可能遺漏了一些東西，但對我來說，任何 NP 問題都可以通過一些 PPT 算法（根據 NP 類的定義）來解決，所以 - 定義針對 PPT 的安全性有什麼意義？我理解這個陳述是錯誤的，但無法找出我到底在錯過什麼。
我認為您誤解了 NP 類中“解決”的含義。
複雜性動物園的定義更準確：如果存在非確定性圖靈機，則問題在NP中 $ M $ 這樣
- 在是的情況下，至少一個計算路徑 $ M $ 接受。
- 在無實例中，所有計算路徑 $ M $ 拒絕。
例如，子集和問題在 NP 中，因為 $ M $ 可以隨機選擇（非確定性地構造）給定整數的子集，將它們相加，然後如果結果為零則接受，否則拒絕。在是的情況下，至少有一個隨機選擇的子集總和為零。在沒有實例的情況下，沒有這樣的子集。
但是現在，你怎麼能用一個PPT算法來解決這個問題呢？您可以創建一個隨機子集，但您不能保證它會成為一個解決方案。