查看“︁承諾問題”︁的源代码

在[[計算複雜度理論]]裡，'''承諾問題'''是一類[[決定性問題]]，其可接受輸入是一個確定大小的集合。<ref>[http://qwiki.stanford.edu/wiki/Zoo_Glossary#P Promise problem] {{webarchive|url=https://web.archive.org/web/20100727083805/http://qwiki.stanford.edu/wiki/Zoo_Glossary |date=2010-07-27 }} at the [[Complexity Zoo]].</ref>與其他的決定性問題不同，承諾問題接受的輸入（確定輸出會是''是''或者''否''的輸入）並不包含所有可能的輸入。直覺上，我們可以說輸入的''承諾''是在一群''是''的輸入或''否''的輸入裡面。如果輸入不屬於這兩個集合，那麼此演算法允許輸出任何答覆。

==正式定義==

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

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

==相關條目==
* [[決定性問題]]
* [[最佳化問題]]
* [[功能性問題]]

==參考資料==
<references/>
===研究===
* [http://www.wisdom.weizmann.ac.il/~oded/PS/prpr.ps ''On Promise Problems (a survey in memory of Shimon Even)'' by Oded Goldreich.] {{Wayback|url=http://www.wisdom.weizmann.ac.il/~oded/PS/prpr.ps |date=20170830050624 }}
* [http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=646133&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D646133 ''A complete promise problem for statistical zero-knowledge'' by Sahai, A.]
* [http://www.sciencedirect.com/science/article/pii/S001999588480056X ''The complexity of promiseproblems with applications to public-key cryptography '' by Shimon Even] {{Wayback|url=http://www.sciencedirect.com/science/article/pii/S001999588480056X |date=20211123021048 }}


[[分類:計算複雜性理論]]