承诺问题

在计算复杂度理论里，承诺问题是一类决定性问题，其可接受输入是一个确定大小的集合。与其他的决定性问题不同，承诺问题接受的输入（确定输出会是是或者否的输入）并不包含所有可能的输入。直觉上，我们可以说输入的承诺是在一群是的输入或否的输入里面。如果输入不属于这两个集合，那么此演算法允许输出任何答复。

正式定义

一个决定性问题可以说与一个语言$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 （页面存档备份，存于互联网档案馆）