承諾問題

维基百科,自由的百科全书
跳转至: 导航搜索

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

正式定義[编辑]

一個決定性問題可以說與一個語言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的迴圈則只需要多項式時間。

相關條目[编辑]

參考資料[编辑]

  1. ^ Promise problem at the Complexity Zoo.

研究[编辑]