エントロピーを使ったXOR補題の証明

嬉しいことに今年STOCに2本の論文を通せたのですが、そのうち一本は、XOR補題（の自然な拡張）をエントロピーを使って証明して、それをaverage-case fine-grained complexityのある数え上げ問題に応用した論文でした。XOR補題は計算量理論では80年代からよく知られている結果で、すでにいくつもの証明方法が知られている（例えば[GNW]が有名）のですが、我々が与えたエントロピーに基づく証明の方が、証明の筋道が直感的にわかり易いのと、（計算量的）疑似エントロピーの良い導入になるので、教育的なのではないかと思っているので、ここで概説します。あくまでも雰囲気がつかめる程度の粒度の記事ですので、細かい詳細は私に直接問い合わせてください（または後日full versionを出すのでそれを参照）。なお、応用についてはここでは省きます。

統計的 vs. 計算量的

平均時計算量という計算量理論の一分野では、情報理論におけるエントロピーなどの概念を「計算量的に」修正したアナロジーを考えることによって、情報理論的な議論に基づいて計算量の結果を証明するということがよく行われます。例えば二つの確率変数$X,Y$の近さを測る指標としてしばし統計距離が使われますが、これは（その確率変数の台を$\Omega$として）

\[
d_{TV}(X,Y)=\max_{D\colon \Omega\to\{0,1\}} \left\{|\Pr[D(X)=1] - \Pr[D(Y)=1]|\right\}
\]
によって定義されます（本来は分布に対して定義されるが、ここでは利便性のため、その分布に従ってサンプリングされた確率変数に対して距離を考えることにする）。ここでは簡単のため$\Omega$は有限集合としています。このとき考える関数$D$を識別者と呼びます。気持ちとしては、識別者は

「与えられた値は$X$と$Y$どちらからサンプリングされたものですか？」

という問題を解こうと頑張っており、その精度の限界値が統計距離となります。すなわち、統計距離が小さいということは、任意の識別者にとって$X$と$Y$が識別できないということになるので、この性質を統計的な識別不可能性（または情報理論的な識別不可能性）と呼びます。

さて、統計距離の定義で考える識別者とは任意の関数を考えていますが、これを

限定的な計算能力を持つ識別者のクラス

に制限することによって新たな識別不可能性の概念を考えることができます。例えば「任意の多項式時間アルゴリズムにとって一様ランダムな文字列と識別できない」といった議論が展開できるわけですが、これを計算量的な識別不可能性と呼び、特に一様ランダムと計算的に識別不可能であるという性質を計算量的疑似ランダムネスと呼びます。

情報理論的には、データ処理不等式により、任意の決定的な関数$f\colon \{0,1\}^n\to\{0,1\}$に対して、分布 $(U_n, f(U_n))$ のエントロピー（ここで$U_n$は$n$ビットの一様ランダムな文字列）は元のランダムシードのエントロピーと一致して必ず$n$のままになる（つまり、決定的な作用を施してもエントロピーは増えない）のですが、計算量理論的な枠組みではある種の計算困難性を仮定すると（計算量理論的）エントロピーを増大できる、という驚くべき結果が知られています。

証明は以前の記事に譲るとして、もう少し深掘りすると、関数$f\colon\{0,1\}^n\to\{0,1\}$が強い平均時困難性を持つとは、任意の効率的な乱択アルゴリズム（注：厳密には非一様なアルゴリズムを考えている）$A$に対して
\[
\Pr_{x\sim U_n,A}[A(x)=f(x)] \le \frac{1}{2} + \varepsilon
\]
を満たすことを言います（$\varepsilon$は文脈依存だがとにかく小さい値。とりあえず$1/\mathrm{poly}(n)$だと思えばよい）。例えば$A$として、$0$ or $1$をランダムに出力するアルゴリズムを考えると正しく$A(x)=f(x)$になる確率はぴったり$1/2$になるわけですが、非自明な精度で$f(x)$を推定しようとすると、その計算能力はすごく沢山要する、というわけです。一方で、右辺が$1$に近い、すなわち
\[
\Pr_{x\sim U_n,A}[A(x)=f(x)] \le 1 - \delta
\]
を満たすとき、弱い平均時困難性を持つと言います。

さて、強い平均時困難性を持つ$f$に対して
\[
(U_n,f(U_n))
\]
という$n+1$ビットの文字列は計算量的疑似ランダムであることが知られており、その逆も成り立ちます。すなわち、関数の計算困難性を計算量的疑似ランダム性で特徴づけられます。例えばNisan-Wigderson生成器を使うと（ある計算量下界の仮定の下での）脱乱択化ができるといった応用があります。

XOR補題

YaoのXOR補題とは、一方向性関数の文脈でYao(1982)で提示された（のちにLevin(1985)で証明が与えられた）結果です。簡単にいうと、弱い平均時困難性を持つ関数 $f\colon \{0,1\}^n\to\{0,1\}$ に対して、別の関数$f^{\oplus k}\colon\{0,1\}^{kn}\to\{0,1\}$を

\[
f^{\oplus k}(x_1,\dots,x_k) = f(x_1) \oplus \dots \oplus f(x_k)
\]

と定義したとき、この関数は（十分大きな$k$に対して）強い平均時困難性を持つ、という結果です。ですので、弱い困難性を持つ関数の下でも、XORをとることでその困難性を増幅させることで、脱乱択といった応用にあてはめることができるようになります。

冒頭でも述べたように、XOR補題の証明は色々知られていて

• 直積定理＋Goldreich-Levin
• hardcore補題
• isolation lemma (Levinによる証明）

などが知られています。本記事で説明する別アプローチの証明は、ZhengのD論(2014)で証明された弱い平均時困難性の計算量的疑似平均最小エントロピー (pseudo average min-entropy)による特徴づけ(PAME theorem)を用います。

疑似（最小）エントロピーとXOR補題

関数 $f$ の強い平均時困難性は疑似ランダム性で特徴づけられると述べましたが、弱い困難性は最小エントロピーの言葉で特徴づけることができます。弱い困難性を持つ関数 $f\colon \{0,1\}^n\to\{0,1\}$ に対して

\[
f(U_n)
\]

という確率変数を考えます。この平均時困難性は、$U_n$が与えられても計算能力が制限された識別者にとっては$f(U_n)$の値が類推できない、すなわちランダムに見えることを保証します。もし$f$が弱い困難性を持つとき、ある程度の精度で類推できるものの、ある程度の確率で間違えます。これを、「$f(U_n)$はある程度のエントロピーを持つ」と解釈します。このエントロピーを疑似エントロピーと呼びます。

もう少しちゃんと述べると、関数 $f$ が疑似エントロピー $\theta$ を持つとは、ある確率変数の組 $(U_n,Z)$ が存在して、

• $(U_n, f(U_n))$ と $(U_n, Z)$ が計算量的に識別不可能
• 条件付き最小エントロピーが$H_{\mathrm{min}}(Z|U_n) \ge \theta$

を満たすことを言います。文脈によってShannonエントロピーを考えることも多いのですが、ここではminエントロピーを考えます（両者の差分については踏み込まないので、詳しくない読者はとりあえず「エントロピーがある」程度の認識で大丈夫です）。

もしも$Z$が一様ランダムなビットだったら疑似ランダム性を持つということになるのですが、この定性的な主張をエントロピーを使って定量的な主張にできます：

定理（Zheng (2014),  informal)

関数 $f\colon \{0,1\}^n\to\{0,1\}$ が弱い困難性を持つ $\iff$ $f$が疑似エントロピー $\log_2 \frac{1}{1-\delta}$ を持つ。

この定理の証明はZhengのD論に書いてあります（私は咀嚼でかなり苦労しました）。この結果は文脈としては[VZ]による、一方向性関数に基づく疑似ランダム生成器の構成の文脈で与えられた結果です（本当は彼らはKL困難性というちょっと異なる概念を考えているが、ほぼ同じ証明でZheng (2014)の結果が示せる）。

ひとまずこの特徴づけを用いると、XOR補題を以下のような流れで証明できます：

1. $f$が弱い困難性を持つので、特徴づけより疑似エントロピーを持つ。
2. $x_1,\dots,x_k \sim U_n$ を独立に選ぶと、$f(x_1),\dots,f(x_k)$はそれぞれ独立でしかも各は$\log_2 \frac{1}{1-\delta}$ の疑似エントロピーを持つ。
3. 情報理論的な議論（本当はフーリエ解析）によって、エントロピーを持つ独立な確率変数の和 $\bmod 2$ はエントロピーが増大する。
4. $k$が十分大きいときはエントロピーはほぼ最大値$1$になる。すなわち$f^{\oplus k}(x_1,\dots,x_k)$は疑似ランダムなので、$f^{\oplus k}$ は強い困難性を持つ。

XOR補題の拡張

XOR補題ではBoolean関数 $f\colon\{0,1\}^n\to\{0,1\}$を考えており、和をとることでBooleanであることを保証するために$\mathbb{F}_2$上での演算を考えていました。我々の論文ではこれを$\mathbb{F}_p$値をとる関数$f\colon\{0,1\}^n\to\mathbb{F}_p$に拡張しました（ただし$p$は素数）。

議論は上のステップ1から4のままです。実はZheng(2014)の結果は$f$がBooleanでなくても成り立つ結果であることを利用します。$p$が素数であるという条件はステップ3において本質で、合成数だと一般には成り立ちません（例えば$\bmod 4$だと、$\{0,2\}$上一様ランダムな確率変数をいくつ足してもエントロピーは変わらない）。

なお、これまで知られているXOR補題の証明はBoolean関数であることを利用しており、例えばhardcore補題ではboostingのために多数決をとるという操作がありますがここでBoolean関数であることを本質的に利用してます（実はZheng (2014)の結果はhardcore補題の拡張とみなすことができます）。Goldreich-Levinは$\mathbb{F}_2$上のHadamard符号のリスト復号アルゴリズムですが、これを$\mathbb{F}_p$に拡張したリスト復号アルゴリズム（[GRS])を用いると、少し異なる主張になってしまいます。

講義資料をCursor+Slidevで作成してみた

私はプログラミング応用という講義＋演習を持っている。昨年はNotionで講義資料を作成したのだが、私はいつもCursorというエディタを使って論文を書いたりしており、最近Slidevというものを知ったので試しにこれらを使って講義資料を準備してみることにした。

今日はプログラミング応用の講義でした. グラフの基本的な定義と全点対最短経路問題について扱いました.https://t.co/dpjbTSJ7ID pic.twitter.com/xMMv5Tek5g

— Nobutaka Shimizu (@knewknowl) October 28, 2025

その結果できたのがこれである。

例えば第６回の講義ではLPの導入として多面体を軽く紹介したが、こんな感じでインタラクティブに可視化できるのが非常に良いと思った。これはVue componentをAIに作ってもらった（なお私はVueを触ったことがない）。

Slidevだとトーク中に画面に書き込みができるので、iPadでスライドショーしても良いと思った。

行列積検算の乱択アルゴリズムと誤り訂正符号

行列積の検証で有名な乱択アルゴリズム (Freivaldsのアルゴリズム) のちょっとした変種が実はSchwartz-Zippelから正当性を直接示せて、とても教育的である、という話。あと、これを決定的にできるのか？について。

 

1. 行列積の検証とFreivaldsのアルゴリズム

Freivaldsの乱択アルゴリズムとは、与えられた三つの$n\times n$行列 $A,B,C$ に対して$AB=C$かどうかを$O(n^2)$時間で乱択を用いて判定する方法です (ただし$A,B,C$は体$K$上の行列で、体の演算に要する計算時間は省略)。具体的には以下のアルゴリズムを考えます:

アルゴリズム1.1

1. 一様ランダムなベクトル $r\sim \{0,1\}^n$ を選ぶ。

2. $ABr \ne Cr$ならば「$AB\ne C$」を出力して終了する。

3. ステップ1-2を何度も繰り返して終了しなかったら「$AB=C$」を出力して終了する。

明らかに$AB=C$を満たすとき、このアルゴリズムは確率1でステップ3で$AB=C$を出力します。一方で$AB\ne C$であったとしても、運が悪いと$AB=C$が出力されうることに注意してください。ところがこの悪い事象の発生確率は小さいことが証明できます:

定理1.2 (Freivalds)

入力が$AB\ne C$を満たす時に上記のステップ1-2を一度実行すると、少なくとも$1/2$の確率で「$AB\ne C$」が出力される。

すなわち、ステップ1-2を$T$回繰り返すと、出力結果が誤っている確率は高$々1/2^T$となります。正当性の証明は他の方の記事がありましたので、そちらを参照します。

そもそも$AB=C$かどうかの判定は、実際に$AB$を計算してそれを$C$と比較すれば良いのですが、行列積の計算が$O(n^2)$時間で行えるかどうかはこの分野の重大な未解決問題です。ところが単に行列積が正しいかどうかの検証は乱択を許すことによって簡単にできてしまうというのが面白いポイントです。このような「行列積を計算する」「行列積の検算を行う」の間にギャップがあるかどうか、つまり簡単に検証できる問題は簡単に解けるか否か?という問題はまさしくP対NP問題の「スケールダウン版」とも言えるでしょう。

2. ちょっとした変種

Freivaldsのアルゴリズムでは
\[ABr = Cr \]
をチェックしましたが、少し修正した以下のアルゴリズムを考えます。ここでは有限体$\mathbb{F}$上の行列を考えます。

アルゴリズム2.1

1. 独立一様ランダムに二つのベクトル $s,r\sim \mathbb{F}^n$ を選ぶ。

2. $r^\top ABs \ne r^\top Cs$ならば「$AB\ne C$」を出力して終了する。

3. ステップ1-2を何度も繰り返して終了しなかったら「$AB=C$」を出力して終了する。

Freivaldsのアルゴリズムとの違いは

1. ランダムベクトルの各成分が$\{0,1\}$ではなく$\mathbb{F}$上でランダムになってる
2. 行列ベクトル積ではなく、二次形式で比較している

という点です。体$\mathbb{F}$が$|\mathbb{F}|\ge 3$なら、その正当性が簡単に証明できます。

定理2.2

$|\mathbb{F}|\ge 3$とする。入力が$AB\ne C$を満たす時にアルゴリズム2.1のステップ1-2を一度実行すると、少なくとも$1/3$の確率で「$AB\ne C$」が出力される。

証明

関数 $F\colon \mathbb{F}^n\times\mathbb{F}^n \to \mathbb{F}$を
\[
F(r,s) = r^\top (AB-C) s\tag{1}
\]
と定義すると、これは$2n$個の変数からなる二次多項式となり、しかも$AB\ne C$であることからこれは非ゼロ多項式である。したがって、Schwartz-Zippelの補題から

\[
\Pr_{r,s\sim\mathbb{F}^n}[F(r,s) = 0] \le \frac{\deg F}{|\mathbb{F}|} \le \frac{2}{3}
\]

となり主張を得ます。

実際に論文に使うのであればアルゴリズム1.1のようなものを使えば良いのですが、個人的にはSchwartz-Zippelの応用としても面白いし証明も単純なのでこちらの方が教育的ではあると考えています。

3. ランダムネスの削減

アルゴリズム1.1や2.1は乱択アルゴリズムですが、決定的に（すなわちランダムネスを使わずに）行列積の（積計算より高速に）検算はできるのでしょうか？これは実は未解決で、最近も論文（例えば[Künnemann, ESA2018]）が出ているようなトピックです。

決定的にするのは難しそうなので、使用するランダムビットを削減する（randomness-efficient）という方針で考えてみましょう。アルゴリズム1.1や2.1はそれぞれ$n$ビットと$O(n\log_2|\mathbb{F}|)$ビットのランダムネスを使っています。これを$0$ビットにできれば脱乱択できたことになります。

ここでは$\mathbb{F}\ge 3n$であれば、簡単に$O(\log |\mathbb{F}|)$ビットに削減できることを示します。このような結果自体は90年代（[Kimbrel, Sinha, IPL1993]）には知られていました。具体的には以下のアルゴリズムを考えます。$\mathbb{F}$は十分大きいと思ってください。

アルゴリズム3.1

1. 体$\mathbb{F}$から一様ランダムに二つの要素 $a,b \sim \mathbb{F}$ を選び、

\begin{align*}
&r = \begin{pmatrix}1 \\ a \\ a^2 \\ \vdots \\ a^{n-1}\end{pmatrix}, \\
&s = \begin{pmatrix}1 \\ b \\ b^2 \\ \vdots \\ b^{n-1} \end{pmatrix}
\end{align*}
とする。

2. $r^\top ABs \ne Cs$ならば「$AB\ne C$」を出力して終了する。

3. ステップ1-2を何度も繰り返して終了しなかったら「$AB=C$」を出力して終了する。

最初の二つのアルゴリズムに比べて、ランダムベクトルの取り方を少し工夫しています。このアルゴリズムは
\[
2\log_2|\mathbb{F}|
\]
ビットのランダムネスを用いています。$\mathbb{F}\ge 3n$の場合には以下のように正当性が担保されます。

定理3.1

$|\mathbb{F}|\ge 3n$とする。入力が$AB\ne C$を満たす時にアルゴリズム3.1のステップ1-2を一度実行すると。少なくとも$1/3$の確率で「$AB\ne C$」が出力される。

証明

定理2.1の証明とほぼ同じです。関数$G\colon\mathbb{F}^2\to\mathbb{F}$を
\[
G(a,b) = (1,a,a^2,\dots,a^{n-1})(AB-C)\begin{pmatrix} 1 \\ b \\ b^2 \\ \vdots \\ b^{n-1} \end{pmatrix} \tag{2}
\]
 で定義します。仮定より$AB\ne C$なので、この関数は非ゼロな二変数多項式であり、その次数は$2n-2\le 2n$です。仮定より$|\mathbb{F}|\ge 3n$なので、Schwartz-Zippelより
\[
\Pr_{a,b\sim\mathbb{F}}[G(a,b)=0] \le \frac{2n}{3n} = \frac{2}{3}
\]
となります。すなわち、各反復でアルゴリズム3.1が誤って「$AB=C$」を出力してしまう確率は高々$1/3$ということになり、主張を得ます。

もっと色々と工夫の余地があり、例えば$r$と$s$を別々にサンプルしていましたが、$\mathbb{F}$が十分大きいという仮定を用いて良いならば$r=s$としてSchwartz-Zippelを適用すればランダムビット長を半分にできると思います。

4. 誤り訂正符号に基づく検算

実は行列積の検算は$AB-C$という行列とみなしたとき、それを誤り訂正符号で符号化し、それが非ゼロ文字列かどうかを確率的に検証している作業とみなすことができます。大雑把にいうと、誤り訂正符号とは文字列から文字列への写像であり、今回の問題設定では行列を符号化するような写像
\[
\mathsf{Enc}\colon \mathbb{F}^{n\times n}\to \mathbb{F}^{N\times N}
\]
であって、

任意の非ゼロ行列$D\in\mathbb{F}^{n\times n}$に対して、$\mathsf{Enc}(D)$は$\delta\cdot N^2$個の非ゼロ成分を含む（$\delta$は適当な定数）

という性質を持つものです。これを用いて行列検算に対する以下のアルゴリズムを考えます：

アルゴリズム4.1

1. $\mathbf{i},\mathbf{j}\sim N$を選ぶ（ここでは$N$は集合として扱う）

2. $\mathsf{Enc}(AB-C)_{\mathbf{i},\mathbf{j}}\ne 0$ならば「$AB\ne C$」を出力

3. ステップ1-2を何度も繰り返して終了しなかったら「$AB=C$」を出力して終了する。

このアルゴリズムはアルゴリズム2.1と3.1を特殊ケースとして含んでいます。例えばアルゴリズム2.1では$N=\mathbb{F}^n$として、式(1)で考えた関数を用いて

\[
\mathsf{Enc}(D)_{r,s} = F(r,s)
\]

で定まる写像を考えることになります。アルゴリズム3.1は、$N=\mathbb{F}$として、式(2)の関数

\[
\mathsf{Enc}(D)_{a,b} = G(a,b)
\]

を考えていることに他なりません。これらの関数が誤り訂正符号として望ましい性質を持つことの証明のみが非自明です。したがって、この非自明な箇所がすでに証明されているような符号を作れば、いろんな行列積検算なアルゴリズムが考えられる、ということになります。

実はこの「行列を誤り訂正符号で行列に符号化する」アイデアは[Hirahara, Shimizu, STOC2025]のアイデア元の一つになっています（この論文を書いてるときに本記事の内容を思いついた）。

約束問題についてのお約束

 ある学会で約束問題について言及したら、その後に約束問題について知らなかった人が意外と多かったのが印象的だった。学生であれば知らないのも仕方ないと思うのだが、分野が少し離れた教員にも「知らなくて勉強になった」旨のお言葉をいただいた。確かに計算量理論の論文とかを読まないとこの用語に出会う機会があまりなさそうだし、我々のアウトリーチ不足ということなのだろう。そこで布教もかねてここで簡単に解説することにした。この調子だと接頭辞に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を出力せよ。

のように、「与えられた入力がグラフであり、かつハミルトン閉路を持つものを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）を出力するように定義される。定義に従って厳密に証明するならばこのような処理も明示する必要があるのだが、これは帰着の数学的に本質的な部分ではないしほとんどの場合は省略される。省略によって特に不便はないのだが、この辺りのことは頭の片隅に置いておく方が良いと思う。

一方で問題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\}^*$に対して

• $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$を解くことをいう。

ここでもやはり、アルゴリズム自体は任意の文字列を入力として受け取ることを想定しており、ただしその場合のアルゴリズムの挙動は不問に伏すことになる。細かいことだが、ここでオラクル$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*}

なお、それぞれの論理式は変数は共有しない独立な二つの論理式である。

通常の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を出力）

1.  変数を$x_1,\dots,x_n$とする。各$i=1,\dots,n$に対して以下を実行する：
1. 論理式$\phi$に$x_i = b$を代入したものを$\phi_b$とする（$b\in\{0,1\}$）
2. オラクル$f$の入力$(\phi_0,\phi_1)$に対する答えが$1$であったとき、$\phi'=\phi_0$とする。それ以外の場合、$\phi'=\phi_1$とする。
3. $\phi$を$\phi'$に置き換えて次のループにうつる
2. 最終的に得られた$\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$になるので検証者は拒否

となる。（証明終）