承诺问题

一个决定性问题可以说与一个语言${\displaystyle L\subseteq \{0,1\}^{*}}$ 互通，这问题接受所有在${\displaystyle L}$ 里面的输入，拒绝所有不在${\displaystyle L}$ 里面的输入。承诺问题则是与两个语言相关，${\displaystyle L_{\text{YES}}}$  and ${\displaystyle L_{\text{NO}}}$ 。此两个语言一定不交集，换句话说，${\displaystyle L_{\text{YES}}\cap L_{\text{NO}}=\varnothing }$ 。此承诺问题接受所有在${\displaystyle L_{\text{YES}}}$ 里面的输入，拒绝所有在${\displaystyle L_{\text{NO}}}$ 里面的输入。${\displaystyle L_{\text{YES}}\cup L_{\text{NO}}}$ 的集合则是此问题的承诺。对于不属于承诺里面的输入则没有规定输出必须是什么。如果承诺等于${\displaystyle \{0,1\}^{*}}$ ，此承诺问题同时也是决定性问题。

许多自然的问题实际上是承诺问题。举例来说，考虑以下问题：给予一个有向图，决定此图是否有长度为10的道路。这问题回答为是的输入是有长度为10道路的有向图，回答否的输入是所没有长度为10道路的有向图，承诺范围则是所有的有向图。在这个例子里面，检查输入是否在承诺范围里面是比较简单的，不过有一些问题可能承诺范围是很难计算的。举例，考虑此问题："给定一个哈密顿图，检查是否有大小为4的循环" ，检查输入是否是哈密顿图是一个NP-hard问题，但是检查是否有大小为4的循环则只需要多项式时间。

• 决定性问题
• 最佳化问题
• 功能性问题

1. ^ Promise problem 互联网档案馆的存档，存档日期2010-07-27. at the Complexity Zoo.

研究

• 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 （页面存档备份，存于互联网档案馆）