ある学会で約束問題について言及したら、その後に約束問題について知らなかった人が意外と多かったのが印象的だった。学生であれば知らないのも仕方ないと思うのだが、分野が少し離れた教員にも「知らなくて勉強になった」旨のお言葉をいただいた。確かに計算量理論の論文とかを読まないとこの用語に出会う機会があまりなさそうだし、我々のアウトリーチ不足ということなのだろう。そこで布教もかねてここで簡単に解説することにした。この調子だと接頭辞にioがつく計算量クラス（io-Pとか）も解説しなければならない日が来る気がする。
色々調べたが、約束問題の用語はArora-Barak本にも載ってなかった。こういうときは大体Goldreichが何とかしてくれるのでGoldreich本を調べたらSection 2.4.1に載ってた。他にも
- Goldreichの記事（これを読めば大体OK）
- Sudanのlecture note（$\mathsf{pr\text{-}BPP}$-完全な問題の話）
- Ta-Shmaのlecture note（$\mathsf{pr\text{-}NP}\cap\mathsf{pr\text{-}coNP}$に属していて、かつ$\mathsf{NP}$-hardな問題の話）
が参考資料となる（誤り訂正符号で有名な人がこういう講義資料を書いてるのはビックリ！）
まずは復習がてら、判定問題の定義を述べる。この記事ではアルファベットは$\{0,1\}$に固定する。
定義1 (判定問題).
集合 $L\subseteq \{0,1\}^*$ を判定問題と呼ぶ。
要するに判定問題とは、アルゴリズムが与えられる任意の文字列に対してYesまたはNoの答えが定まっている問題である。では、次の問題は判定問題だろうか？
問題2 (ハミルトン閉路問題).
与えられたグラフ $G=(V,E)$ はハミルトン閉路を含むならばYes、そうでなければNoを出力せよ。
ほとんどの文脈では、ここでは与えられる入力が暗にグラフであることを仮定するのが自然である。しかし、一般にアルゴリズム（チューリング機械）は必ずしもグラフと解釈できない文字列が与えられる。そのような場合、上記の問題2の記述だけでは「グラフと解釈できない文字列が与えられた場合の答えをどうするか？」が明示されていないので、問題2だけを見るとこれは判定問題とは言えないのである。
そこで我々は暗に問題２は
問題2' (ハミルトン閉路問題).
与えられた文字列 $x\in\{0,1\}^*$ は、その長さ$|x|$が平方数であり、$n=\sqrt{|x|}$に対して、
\[
A[i][j] = x[n*i+j] \quad \text{(0-index)}
\]
で定まる行列$A\in\{0,1\}^{n\times n}$が対称行列かつ、それを隣接行列としてもつグラフがハミルトン閉路を含むならばYes、それ以外の場合はNoを出力せよ。
\[
A[i][j] = x[n*i+j] \quad \text{(0-index)}
\]
で定まる行列$A\in\{0,1\}^{n\times n}$が対称行列かつ、それを隣接行列としてもつグラフがハミルトン閉路を含むならばYes、それ以外の場合はNoを出力せよ。
のように、「与えられた入力がグラフであり、かつハミルトン閉路を持つものをYesインスタンスとみなし、それ以外をNoとする」ことによってハミルトン閉路問題を判定問題として扱うことができるのである。このようにフォーマルに判定問題として扱うことによって初めて我々はクラス$\mathsf{P}$やクラス$\mathsf{NP}$に属するか否か、また$\mathsf{NP}$-完全かどうかの議論が可能になるのである。
確かに論文を書くときにいちいち問題2'のような書き方をするのは面倒なので、基本的には論文や口頭発表などでは問題2の形で議論していく。判定問題の計算量クラスを議論する際は常に問題2'のように明示的な判定問題を議論していることを念頭に置くと良い。
例えば、グラフに関する二つの問題のNP完全性の証明とかで考えるカープ帰着を考えてみよう。カープ帰着とは形式的には多項式時間で計算でき、答えを保存する関数
\[
f \colon \{0,1\}^* \to \{0,1\}^*
\]
である。我々は一方の問題のインスタンス$x$をもう一方の問題のインスタンス$f(x)$に変換するわけだが、基本的には元のインスタンスは常にグラフであることを想定し、変換後も常にグラフになるような構成を考える。しかしながら判定問題を議論する以上は元のインスタンス$x$が必ずしもグラフとは限らず、そういう場合は問題2'のような定義では元問題の自明なNoインスタンスであるため、$f(x)$は自明なNoインスタンス（$x$そのものにすればグラフでないので自明にNo）を出力するように定義される。定義に従って厳密に証明するならばこのような処理も明示する必要があるのだが、これは帰着の数学的に本質的な部分ではないしほとんどの場合は省略される。省略によって特に不便はないのだが、この辺りのことは頭の片隅に置いておく方が良いと思う。
\[
f \colon \{0,1\}^* \to \{0,1\}^*
\]
である。我々は一方の問題のインスタンス$x$をもう一方の問題のインスタンス$f(x)$に変換するわけだが、基本的には元のインスタンスは常にグラフであることを想定し、変換後も常にグラフになるような構成を考える。しかしながら判定問題を議論する以上は元のインスタンス$x$が必ずしもグラフとは限らず、そういう場合は問題2'のような定義では元問題の自明なNoインスタンスであるため、$f(x)$は自明なNoインスタンス（$x$そのものにすればグラフでないので自明にNo）を出力するように定義される。定義に従って厳密に証明するならばこのような処理も明示する必要があるのだが、これは帰着の数学的に本質的な部分ではないしほとんどの場合は省略される。省略によって特に不便はないのだが、この辺りのことは頭の片隅に置いておく方が良いと思う。
一方で問題2のように、与えられた入力が常に何らかの構造（例えばグラフ）を持つことを仮定するという枠組みを考えたい場合も多々ある。計算量理論ではこのような問題を約束問題という。形式的には以下のように定義される：
定義3 (約束問題）
約束問題とは、組$(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$である。ここで、$\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}}\subseteq\{0,1\}^*$は、$\Pi_{\mathrm{yes}} \cap \Pi_{\mathrm{no}} = \emptyset$ を満たす。
また、$\Pi_{\mathrm{yes}}\cup \Pi_{\mathrm{no}}$を約束という。
アルゴリズム$A$が約束問題$\Pi=(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$を解くとは、任意の入力$x\in\{0,1\}^*$に対して
また、$\Pi_{\mathrm{yes}}\cup \Pi_{\mathrm{no}}$を約束という。
アルゴリズム$A$が約束問題$\Pi=(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$を解くとは、任意の入力$x\in\{0,1\}^*$に対して
- $x\in\Pi_{\mathrm{yes}}$ならば$A(x)=1$
- $x\in\Pi_{\mathrm{no}}$ならば$A(x)=0$
が成り立つことをいう。
例えば問題2は、その文面を読むと入力がグラフであると約束されているため、形式的には約束問題と呼ぶべき問題なのである。一般に与えられた$x\in\{0,1\}^*$が約束に属するかどうかが簡単に判定できれば、本質的に複雑性に差異は生まれない。例えば問題2と問題2'は、与えられた入力がグラフの隣接行列かどうかは簡単にチェックできるので、問題2を見たときに暗に問題2'とみなして判定問題として扱うことで、「問題2はNP完全である」という主張はすんなりと受け入れられるわけである。
また、約束問題では、与えられたインスタンスが約束に属さない場合は正解は定義されず、そのような入力上ではアルゴリズムはどのような挙動をしても良い（例えば停止する必要すらない）とされる。
約束問題に対しても$\mathsf{P}$や$\mathsf{NP}$の概念が定義でき、$\mathsf{pr}\text{-}\mathsf{P}$や$\mathsf{pr}\text{-}\mathsf{NP}$などと呼ばれる（記法は文献によって色々異なる）。
定義4 (約束問題の計算量クラス）
約束問題$\Pi=(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$は、ある多項式時間アルゴリズム$A$が存在して$A$が$\Pi$を解くとき、クラス$\mathsf{pr}\text{-}\mathsf{P}$に属するといい、そのような約束問題全体の集合を$\mathsf{pr}\text{-}\mathsf{P}$と表す。
また、ある定数$c>0$と多項式時間アルゴリズム$V$が存在して、任意の$x\in\{0,1\}^*$に対して
- $x\in \Pi_{\mathrm{yes}}$ならば、ある$y\in\{0,1\}^{|x|^c}$が存在して$V(x,y)=1$
- $x\in \Pi_{\mathrm{no}}$あらば、任意の$y\in\{0,1\}^{|x|^c}$に対して$V(x,y)=0$
を満たすとき、クラス$\mathsf{pr}\text{-}\mathsf{NP}$に属するといい、そのような約束問題全体の集合を$\mathsf{pr}\text{-}\mathsf{NP}$と表す。
また、上記のyes/noを反転させて定義されるクラスをクラス$\mathsf{pr}\text{-}\mathsf{coNP}$という。
約束が全体集合となる（すなわち$\Pi_{\mathrm{yes}}\cup\Pi_{\mathrm{no}}=\{0,1\}^*$を満たす）ときは判定問題のクラス$\mathsf{P},\mathsf{NP}$の定義と合致することがわかるだろう。
カープ帰着やクック帰着（チューリング帰着）についても同様に定義される。クック帰着については、オラクルへのクエリが約束に属さない場合はオラクルは何を出力しても良いように修正している：
定義5 (帰着）
二つの約束問題$\Pi=(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$と$\Pi'=(\Pi'_{\mathrm{yes}},\Pi'_{\mathrm{no}})$に対し、$\Pi$が$\Pi'$にカープ帰着できるとは、以下を満たす関数 $f\colon \{0,1\}^*\to\{0,1\}^*$ が存在することをいう：
- $f$を計算する多項式時間アルゴリズムが存在する。
- 任意の$x\in\Pi_{\mathrm{yes}}$に対し、$f(x)\in\Pi'_{\mathrm{yes}}$
- 任意の$x\in\Pi_{\mathrm{no}}$に対し、$f(x)\in\Pi'_{\mathrm{no}}$
同様に、$\Pi$が$\Pi'$にクック帰着できるとは、あるオラクルアルゴリズム$A^f$が存在して、オラクル$f\colon\{0,1\}^*\to\{0,1\}$が
\begin{align*}
&x \in \Pi'_{\mathrm{yes}} \Rightarrow f(x)=1,\\
&x \in \Pi'_{\mathrm{no}} \Rightarrow f(x)=0
\end{align*}
を満たす任意の$f$について、$A^f$は$\Pi$を解くことをいう。
\begin{align*}
&x \in \Pi'_{\mathrm{yes}} \Rightarrow f(x)=1,\\
&x \in \Pi'_{\mathrm{no}} \Rightarrow f(x)=0
\end{align*}
を満たす任意の$f$について、$A^f$は$\Pi$を解くことをいう。
ここでもやはり、アルゴリズム自体は任意の文字列を入力として受け取ることを想定しており、ただしその場合のアルゴリズムの挙動は不問に伏すことになる。細かいことだが、ここでオラクル$f$はアルゴリズムではなく関数として扱うので、例えば「停止性判定問題を解くオラクル」といった言葉が意味を持つことに注意されたい。
このような帰着に対して完全性や困難性といった概念が定義できる。
グラフの例で述べたように、約束を満たすかどうかの判定が簡単ならば両者に本質的な差異は生まれない。一方でこの判定が難しい場合は興味深い現象が発生する。例として、以下の約束問題 $\Pi$ を考えてみよう：
定義6（充足可能性択一問題）
一方が充足可能、もう一方が充足不可能であると約束されている二つの論理式 $\phi_0,\phi_1$ が与えられたとき、どちらが充足可能かを判定せよ。すなわち
\begin{align*}
&\Pi_{\mathrm{yes}} = \{(\phi_0,\phi_1)\colon \phi_0\in\mathrm{SAT}\text{ and }\phi_1 \in \mathrm{UNSAT} \}, \\
&\Pi_{\mathrm{no}} = \{(\phi_0,\phi_1) \colon \phi_0\in\mathrm{UNSAT} \text{ and }\phi_1 \in \mathrm{SAT} \}.
\end{align*}
&\Pi_{\mathrm{yes}} = \{(\phi_0,\phi_1)\colon \phi_0\in\mathrm{SAT}\text{ and }\phi_1 \in \mathrm{UNSAT} \}, \\
&\Pi_{\mathrm{no}} = \{(\phi_0,\phi_1) \colon \phi_0\in\mathrm{UNSAT} \text{ and }\phi_1 \in \mathrm{SAT} \}.
\end{align*}
なお、それぞれの論理式は変数は共有しない独立な二つの論理式である。
通常のSAT問題は$\mathsf{NP}$完全であり、広く信じられている$\mathsf{NP}\ne\mathsf{coNP}$を仮定すれば$\mathrm{SAT}\not\in\mathsf{coNP}$となる。この記事の最後で証明するが、$\mathsf{NP}\cap\mathsf{coNP}$に属していて、かつ$\mathsf{NP}$困難の問題が存在すれば$\mathsf{NP}=\mathsf{coNP}$が成り立つ。
主張7.
充足可能性択一問題は$\mathsf{pr}\text{-}\mathsf{NP}\cap \mathsf{pr}\text{-}\mathsf{coNP}$に属する。さらにこの問題は$\mathsf{NP}$困難である。
「属する」の部分は簡単に確認できる。YesインスタンスだろうがNoインスタンスだろうが、どちらか一方は充足可能であることが約束されているので、そちらの充足割り当てを証拠とすれば、答えがYes/Noに限らず常に証拠を持って来れる。
$\mathsf{NP}$困難性についても、以下のようにすればSATを解くことができる：充足可能性択一問題を解くオラクルを $f$ とする。SATのインスタンス$\phi$に対して（論理式でない場合はNoを出力）
- 変数を$x_1,\dots,x_n$とする。各$i=1,\dots,n$に対して以下を実行する：
- 論理式$\phi$に$x_i = b$を代入したものを$\phi_b$とする（$b\in\{0,1\}$）
- オラクル$f$の入力$(\phi_0,\phi_1)$に対する答えが$1$であったとき、$\phi'=\phi_0$とする。それ以外の場合、$\phi'=\phi_1$とする。
- $\phi$を$\phi'$に置き換えて次のループにうつる
- 最終的に得られた$\phi$は全変数に値が代入されているため$0$または$1$である。その値をそのまま出力する。
SATインスタンス$\phi$が充足不可能であったとすると、各$x_i$にどのような値を代入しても最終的に$\phi=0$になるので、確かにオラクルアルゴリズムは$0$を正しく出力する。
一方で$\phi$が充足可能であったとする。このとき、反復で構成される$\phi'$は常に充足可能であることを証明する。そのために途中で考える$(\phi_0,\phi_1)$について場合わけを考える：
- $\phi_0,\phi_1\in\mathrm{SAT}$のとき：$x_i$にどちらを代入しても充足可能になるので$\phi'$も充足可能である。
- $\phi_0\in\mathrm{SAT},\phi_1\in\mathrm{UNSAT}$のとき：このときは$(\phi_0,\phi_1)$は充足可能性択一問題のYesインスタンスなのでオラクルは必ず$1$を返す。したがって$\phi'=\phi_0\in\mathrm{SAT}$となる。逆の場合も同様。
以上より、確かに択一問題が解ければSATも解けることになるので主張は示された。（証明終）
最後に、以下の主張を証明しておく。これによって、約束問題と判定問題のギャップが明確になるだろう：
主張8.
任意の判定問題$L\in\mathsf{NP}\cap\mathsf{coNP}$に対し、$P^L\subseteq \mathsf{NP}\cap\mathsf{coNP}$。
この主張から、もしもNP困難な判定問題$L\in\mathsf{NP}\cap\mathsf{coNP}$が存在するならば、$\mathsf{NP}\subseteq P^{L} \subseteq \mathsf{coNP}$となり、特に$\mathsf{NP}=\mathsf{coNP}$が従う。
主張の証明：
$P^L$は補問題で閉じているので、$P^L\subseteq\mathsf{NP}$を示せば十分である。そこで任意の$L'\in P^L$を固定し、$L'\in\mathsf{NP}$を示す。$L'\in P^L$より、$L'$を解くオラクルアルゴリズム $A^L$ が存在する。$L'$を検証する証拠を以下で構成する。
Yesインスタンス$x$に対し、$A^L(x)=1$となる。このとき以下を全て証拠として持つことにする：
- オラクル$L$へのクエリ $q_1,\dots,q_m\in\{0,1\}^*$ ($A$は多項式時間なので、これらのクエリは多項式長）
- 各クエリ $q_i$ に対するオラクルの返答 $a_i \in \{0,1\}$
- $a_i=1$のとき、$q_i \in L$ であることの証拠 ($L\in \mathsf{NP}$なのでそのような証拠が存在する）
- $a_i = 0$のとき、$q_i\not\in L$であることの証拠（$L \in \mathsf{coNP}$なので、同様にとれる）
すなわち$L'$のNP検証者としては、オラクルアルゴリズム$A^L$を、証拠をオラクルの返答とみなして模倣し、最終的にそれが$1$を出力したら受理するというものを考えればよい。
$x$がYesインスタンスのときは確かに上記の証拠を用意できる。Noインスタンスに対しては$A^L(x)=0$になるので、
- $A^L$を模倣する途中で証拠との整合性がとれなくなり、この時点で検証者は拒否
- もしくは整合性が完全に取れたとすると$A^L(x)=0$になるので検証者は拒否
となる。（証明終）
