承諾問題

在計算複雜度理論裏，承諾問題是一類決定性問題，其可接受輸入是一個確定大小的集合。與其他的決定性問題不同，承諾問題接受的輸入（確定輸出會是是或者否的輸入）並不包含所有可能的輸入。直覺上，我們可以說輸入的承諾是在一群是的輸入或否的輸入裏面。如果輸入不屬於這兩個集合，那麼此演算法允許輸出任何答覆。

正式定義

一個決定性問題可以說與一個語言$L\subseteq \{0,1\}^{*}$互通，這問題接受所有在$L$裏面的輸入，拒絕所有不在$L$裏面的輸入。承諾問題則是與兩個語言相關，$L_{\text{YES}}$ and $L_{\text{NO}}$。此兩個語言一定不交集，換句話說，$L_{\text{YES}}\cap L_{\text{NO}}=\varnothing$。此承諾問題接受所有在$L_{\text{YES}}$裏面的輸入，拒絕所有在$L_{\text{NO}}$裏面的輸入。$L_{\text{YES}}\cup L_{\text{NO}}$的集合則是此問題的承諾。對於不屬於承諾裏面的輸入則沒有規定輸出必須是什麼。如果承諾等於$\{0,1\}^{*}$，此承諾問題同時也是決定性問題。

範例

許多自然的問題實際上是承諾問題。舉例來說，考慮以下問題：給予一個有向圖，決定此圖是否有長度為10的道路。這問題回答為是的輸入是有長度為10道路的有向圖，回答否的輸入是所沒有長度為10道路的有向圖，承諾範圍則是所有的有向圖。在這個例子裏面，檢查輸入是否在承諾範圍裏面是比較簡單的，不過有一些問題可能承諾範圍是很難計算的。舉例，考慮此問題："給定一個哈密頓圖，檢查是否有大小為4的迴圈" ，檢查輸入是否是哈密頓圖是一個NP-hard問題，但是檢查是否有大小為4的迴圈則只需要多項式時間。

相關條目

• 決定性問題
• 最佳化問題
• 功能性問題

參考資料

研究

• On Promise Problems (a survey in memory of Shimon Even) by Oded Goldreich. （頁面存檔備份，存於互聯網檔案館）
• A complete promise problem for statistical zero-knowledge by Sahai, A.
• The complexity of promiseproblems with applications to public-key cryptography by Shimon Even （頁面存檔備份，存於互聯網檔案館）