約束の問題

計算複雑性理論において、約束問題とは、入力がすべての可能な入力の特定のサブセットに属することが約束される決定問題の一般化である。 ^[1]決定問題とは異なり、yesインスタンス（アルゴリズムがyes を返さなければならない入力）とnoインスタンスは、すべての入力のセットを使い尽くすわけではない。直感的には、アルゴリズムは、入力が確かにyesインスタンスまたはnoインスタンスのセットに属することが約束されている。 yesでも​​ noでもない入力が存在する可能性がある。約束問題を解くアルゴリズムにそのような入力が与えられた場合、アルゴリズムは何でも出力することが許可され、停止しない可能性もある。

決定問題は言語 に関連付けることができます。ここで、問題は 内のすべての入力を受け入れ、 にないすべての入力を拒否することです。約束問題の場合、とという2 つの言語があり、これらは と互いに素でなければなりません。つまり、 のすべての入力が受け入れられ、 のすべての入力が拒否されることになります。この集合は約束と呼ばれます。入力が約束に属していない場合、出力には要件はありません。約束 が に等しい場合、これも決定問題であり、約束は自明であると言われます。 ${\displaystyle L\subseteq \{0,1\}^{*}}$${\displaystyle L}$${\displaystyle L}$${\displaystyle L_{\text{はい}}}$${\displaystyle L_{\text{NO}}}$${\displaystyle L_{\text{YES}}\cap L_{\text{NO}}=\varnothing }$${\displaystyle L_{\text{はい}}}$${\displaystyle L_{\text{NO}}}$${\displaystyle L_{\text{はい}}\cup L_{\text{いいえ}}}$${\displaystyle \{0,1\}^{*}}$

多くの自然な問題は、実は約束の問題です。たとえば、次の問題を考えてみましょう。有向非巡回グラフ が与えられた場合、グラフに長さ 10のパスがあるかどうかを判断します。yesインスタンスは長さ 10 のパスを持つ有向非巡回グラフですが、noインスタンスは長さ 10 のパスを持たない有向非巡回グラフです。約束は有向非巡回グラフの集合です。この例では、約束の確認は簡単です。特に、与えられたグラフが巡回かどうかの確認は非常に簡単です。ただし、約束されたプロパティの評価は難しい場合があります。たとえば、「ハミルトン グラフが与えられた場合、グラフにサイズ 4 のサイクルがあるかどうかを判断してください」という問題を考えてみましょう。この場合、約束の評価はNP 困難ですが、サイズ 4 のサイクルの確認は多項式時間で実行できるため、約束の問題は簡単に解決できます。

• 計算上の問題
• 決定問題
• 最適化問題
• 検索の問題
• 数え上げ問題（複雑さ）
• 機能の問題
• TFNP

• Goldreich, Oded (2006)。「Promise Problems について (概要)」。理論計算機科学: Shimon Even を偲んでのエッセイ。LNCS。第 3895 巻。pp. 254–290。doi : 10.1007/11685654_12。
• Sahai, A.; Vadhan, SP (1997). 「統計的ゼロ知識のための完全な約束問題」. FOCS 1997 . pp. 448–457. CiteSeerX  10.1.1.34.6920 . doi :10.1109/SFCS.1997.646133.
• Even, Shimon; Selman, Alan L .; Yacobi, Yacov (1984). 「約束問題の複雑さと公開鍵暗号への応用」.情報と制御. 61 (2): 159–173. doi :10.1016/S0019-9958(84)80056-X.