2月に冬のLAに参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました.
自分の発表には全く関係ないことですが, LAに参加していてValiant--Vaziraniの定理がいまいち知名度がないということを初めて認識しました. これまでもこの定理をブログ記事にしたいと常々思っていたので重い腰をあげて解説しようと思います.
充足可能性判定問題 (SAT)とUSAT
$n$個の変数$x_1,\dots,x_n$を持つ論理関数$\phi\colon\{0,1\}^n\to\{0,1\}$が与えられたときに$\phi(x)=1$を満たす$x$が存在するかを問う問題を充足可能性判定問題(SAT)と言います (ここでは論理式は回路として与えられると思ってください. CNFでもOKです.).
一般に充足可能性判定問題は解の存在性を判定するだけです. では特殊ケースとして「充足割当が高々一つしか存在しないことが保証されている論理関数」に対するSATは効率的に解けるのでしょうか？
このような判定問題をUSAT (unique SAT)と言います. 厳密にはUSATは約束問題です. すなわち, 与えられた論理関数$\phi$が以下で定義される二つの集合$U_{\mathrm{yes}},U_{\mathrm{no}}$のどちらに属するかを判定する問題です:
\begin{align*}
&U_{\mathrm{yes}} = \{\phi\colon \phi\text{ has a unique satisfying assignment}\},\\
&U_{\mathrm{no}} = \{\phi\colon \phi\text{ has no satisfying assignments}\}.
\end{align*}
与えられた$\phi$がこの二つの集合どちらにも属していない場合はYES/NOどちらを答えても正解としてみなします. $U_{\mathrm{yes}}, U_{\mathrm{no}}$はdisjointですが$U_{\mathrm{yes}}\cup U_{\mathrm{no}}$は必ずしも入力全体の集合になるわけではありません. yesインスタンス全体とnoインスタンス全体の和集合が入力全体になる決定問題を判定問題と呼び, そうとは限らない決定問題を計算量理論では約束問題 (promise problem)といいます (約束問題は判定問題を特殊ケースとして含んでいます). 細かい注意ですが, $\mathsf{P}$とか$\mathsf{NP}$は判定問題の計算量クラスなので「$\mathrm{USAT}\in\mathsf{P}$」という主張は文法がおかしく, 正しくは 「$\mathrm{USAT}\in\mathsf{prP}$」です (promise P).
Valiant--Vaziraniの定理
Valiant--Vaziraniの定理とは乱択を許したときにUSATがSATに帰着できることを主張する定理です. 例えばその帰結として
USATが多項式時間で解ける $\Rightarrow$ SATが乱択多項式時間で解ける
が得られますので, USATはいわば"乱択NP困難" (これはofficialな用語ではない!)ということになります. ValiantはPAC学習を定義したりマッチング数え上げの#P困難性を証明した方で, Vaziraniは近似アルゴリズムの本で有名なVaziraniです. どちらも非常に偉大な方です. 原著論文はこちらです.
定理1 (Valiant--Vaziraniの定理)
論理関数を別の論理関数に変換する多項式時間乱択アルゴリズム$R$とある多項式$p$が存在し, 任意の論理関数$\phi\colon\{0,1\}^n\to\{0,1\}$に対し,
- $\phi\in \mathrm{SAT}$ ならば, $\Pr[R(\phi)\in U_{\mathrm{yes}}]\ge \frac{1}{p(n)}$.
- $\phi\not\in\mathrm{SAT}$ ならば, 確率1で$R(\phi)\in U_{\mathrm{no}}$.
ただし$\mathrm{SAT}$は充足可能な論理式全体を表す.
仮にUSATが多項式時間アルゴリズム$A$で解けたとしましょう. このアルゴリズム$A$を定理1のアルゴリズム$R$と組み合わせることで以下のようにしてSATを解くことができます:
- 与えられた論理関数$\phi$を入力として$R$を走らせ, 別の論理関数$\phi'$を得る.
- $\phi'$を入力として$A$を走らせ, YESを出力したらそのままYESを出力する.
- そうでなければステップ1に戻る. これを$100p(n)$回繰り返しても終わらない場合はNOを出力する.
上述の乱択アルゴリズムは任意のSATインスタンス$\phi$に対し99%の確率で正解を出力します. 元の$\phi$が$\phi\in\mathrm{SAT}$ならば, $100p(n)$回の繰り返しの中で全て$R(\phi)\not\in U_{\mathrm{no}}$となってしまう確率は$(1-1/p(n))^{100p(n)}\le \exp(-100)<0.01$だからです (ここでは$\forall x\in\mathbb{R},1+x\le \exp(x)$を使っている).
証明のアイデア
証明の直感を養うために, 効率性を無視した次の帰着を考えます:
- $\phi\colon\{0,1\}^n\to\{0,1\}$を与えられた論理関数とする.
- 適切に設定されたパラメータ$m$に対し, $f\colon\{0,1\}^n\to\{0,1\}^m$を一様ランダムな関数とする (すなわち, 各$x\in\{0,1\}^n$に対して$f(x)$は独立一様ランダムな$m$ビット文字列を出力する関数.
- $\phi'(x) = \phi(x) \land \langle f(x)=1^m \rangle$とする. ここで$\langle E \rangle$は事象$E$の指示関数とする.
明らかに, $\phi$が充足可能でないならば$\phi'$もまた充足可能ではありません. 一方で$\phi$が充足可能であるとき, 充足割当の個数を$N$とすると, $\phi'$の充足割当の個数$N'$は$\mathbb{E}[N']=N/2^m$を満たします. ですので, $m=\log_2 N$とすれば期待値が$1$になります. $N'$の実際の分布は二項分布$\mathrm{Bin}(N,1/N)$であり, $\Pr[\mathrm{Bin}(N,1/N)=1]\ge \mathrm{const}$が成り立つ ($N\to\infty$の極限では$\mathrm{Bin}(N,1/N)\to\mathrm{Po}(1)$に収束する). なお, ステップ3の$\langle f(x)=1^m \rangle$における$1^m$は特に$1^m$である必然性はありません.
この帰着では$N$の値を知る必要があるのですが, そこもまたランダムに与えれば良いです. 一様ランダムに$m\sim[n]$をとると確率$1/n$で$2^{m-1}\le N \le 2^m$を満たします. この$m$を用いて上の帰着を実行すれば, 同じようなポアソン近似により確率$\mathrm{const}\cdot (1/n) \ge \mathrm{poly}(n)$で$\phi'\in U_{\mathrm{yes}}$を満たすことが確認できます.
しかしながら, 上述の帰着では一様ランダムな関数$f$をサンプリングするには少なくとも$m2^n$ビットのランダムビットが必要なので, 指数時間かかってしまいます. そこでこのサンプリングに必要なランダムビット数を$\mathrm{poly}(n)$ビットまで削減することを目指していくことになります. すなわち, 一様ランダムな関数と同等の性質を持つ別のランダム関数を短いランダムシード長でサンプリングすることを目標にします.
ペア独立性
この記事では確率変数といえばデフォルトで離散値をとるものを考えます (計算機では全てが離散で処理されるので).
二つの確率変数$X,Y$は, 任意の$x,y$に対して$\Pr[X=x\text{ and }Y=y]=\Pr[X=x]\Pr[Y=y]$を満たすとき独立であると言います. より一般に確率変数$X_1,\dots,X_n$が独立であると言ったとき, それは任意の$x_1,\dots,x_n$に対して
\begin{align*}
\Pr[X_i = x_i \text{ for all }i\in [n]]=\prod_{i\in [n]}\Pr[X_i=x_i]
\end{align*}
を意味します. 独立という代わりに相互に独立(mutually indepedent)であると言うこともあります.
一方で, 任意の$1\le i<j\le n$と$x_i,x_j$に対し
\begin{align*}
\Pr[X_i=x_i\text{ and }X_j=x_j]=\Pr[X_i=x_i]\Pr[X_j=x_j]
\end{align*}
が成り立つとき, $X_1,\dots,X_n$は
ペア独立 (
pairwise independent) であると言います. pairwise independenceにはこれといったスタンダードな和訳は(私の知る限り)ないと思いますが, ここでは
こちらのページから拝借しております. なお, 上の定義では$i\neq j$としていることに注意してください.
ペア独立ハッシュ関数
ハッシュ関数と聞くとPythonの辞書などを想起されますが, 計算量の文脈ではハッシュ関数と言ったらある分布に従って生成されたランダムな関数を指すものと思ってください.
ランダムな関数$f\colon\{0,1\}^n\to\{0,1\}^m$に対し, $2^n$個の確率変数$f(0^n),\dots,f(1^n)$がペア独立であるとき, $f$はペア独立ハッシュ関数であると言います.
単に$f$がペア独立ハッシュ関数であると言った場合は単にペア独立性だけを指しますが, しばしば, 任意に固定した$x\in\{0,1\}^n$に対して$f(x)$の分布は一様ランダムであることが多いです.
例えば, 証明のアイデアで考えた「各$x\in\{0,1\}^n$に対し独立一様ランダムな$m$ビット文字列を$f(x)$として出力する関数」はペア独立ハッシュ関数です. この例は生成に指数長のランダムシードを要しますが, よりrandomness-efficientなものも構成できます.
ランダムな直線
有限体$\mathbb{F}=\mathbb{F}_{2^n}$上の関数を考えます. ここでは$\mathbb{F}_{2^n}$の厳密な定義を理解しておく必要はありません. 掛け算と足し算ができて, 非ゼロな元では割り算ができて, これらの演算が$n$に関する多項式時間でできて, しかも$|\mathbb{F}_{2^n}|=2^n$になっているので$\{0,1\}^n$と一対一対応がある, という事実だけを使います. 一様ランダムに$a,b\sim\mathbb{F}$をサンプリングしてランダム関数$f\colon \mathbb{F}\to\mathbb{F}$を
\[f(x) = ax+b\]
で定めます. 有限体を$\mathbb{F}_{2^n}\cong \{0,1\}^n$で同一視すると$f$は$n$ビット文字列から$n$ビット文字列への関数とみなせます.
補題2.
一様ランダムな$a,b\sim\mathbb{F}$に対し, $f\colon x\mapsto ax+b$はペア独立ハッシュ関数である. すなわち, $|\mathbb{F}|$個の確率変数$(f(x))_{x\in \mathbb{F}}$はペア独立である. さらに, 固定した$x\in \mathbb{F}$に対して$f(x)$の分布は$\mathbb{F}$上一様ランダムである.
証明. 任意の$x_1\neq x_2\in \mathbb{F}$と$y_1,y_2\in\mathbb{F}$に対して
\[
\Pr[f(x_1)=y_1 \text{ and }f(x_2)=y_2] = \Pr[f(x_1)=y_1]\Pr[f(x_2)=y_2]
\]
を示せば良いです. $f(x_i)=y_i$ ($i=1,2$)という等式を行列を用いて表すと
\[
\begin{bmatrix}
x_1 & 1 \\
x_2 & 1 \\
\end{bmatrix}
\begin{bmatrix}
a \\
b
\end{bmatrix}
=
\begin{bmatrix}
y_1 \\
y_2
\end{bmatrix}
\]
となります. ヴァンデルモンドの行列式から係数行列は正則なので, $[a\,b]^{\top}$はある特定のベクトルになっていなければならず, $a,b\sim\mathbb{F}$は一様ランダムなのでこれが起こる確率は$1/|\mathbb{F}|^2$となります.
一方で$\Pr[f(x_i)=y_i]=1/|\mathbb{F}|$なので, 確かに$(f(x))_{x\in \mathbb{F}}$はペア独立であることが確認されました. (証明終)
補題2で構成したペア独立ハッシュ関数は$n$ビット文字列から$n$ビット文字列への写像でしたが, 出力の$n$ビットのうち最初の$m$ビットだけを取り出した ($m\le n$) 文字列を出力するようにすれば, 値域を$\{0,1\}^m$にしつつペア独立になるようにできます.
補題3.
ペア独立ハッシュ関数$f\colon \{0,1\}^n\to\{0,1\}^n$と固定したパラメータ$m\le n$に対し, $f'(x)\in\{0,1\}^m$を$f(x)$の先頭$m$ビットからなる文字列と定義する. このとき, $f'\colon\{0,1\}^n\to\{0,1\}^m$はペア独立ハッシュ関数である.
証明. 確率変数$(f(x))_{x\in\{0,1\}^n}$がペア独立であることを利用して$(f'(x))_{x\in\{0,1\}^n}$がペア独立であることを示します. ペア独立性の定義から, 任意の$x_1\neq x_2\in\{0,1\}^n$と$y_1,y_2\in\{0,1\}^m$に対して
\[
\Pr[f'(x_1)=y_1\text{ and }f'(x_2)=y_2]=\Pr[f'(x_1)=y_1]\Pr[f'(x_2)=y_2]
\]
が成り立つことを示せばよいです.
文字列$y\in\{0,1\}^m$に対して, 先頭$m$ビットが$y$になるような$n$ビット文字列の全体を$S(y)\subseteq\{0,1\}^n$とします. $f'(x)$は$f(x)$の先頭$m$文字を取り出すことから, $f'(x)=y \iff f(x)\in S(y)$です. 従って
\begin{align*}
\Pr[f'(x_1)=y_1\text{ and }f'(x_2)=y_2] &= \sum_{z_1\in S(y_1),z_2\in S(y_2)} \Pr[f(x_1)=z_1\text{ and }f(x_2)=z_2] \\
&= \sum_{z_1\in S(y_1),z_2\in S(y_2)} \Pr[f(x_1)=z_1]\Pr[f(x_2)=z_2] & & \text{pairwise independence of $f$} \\
&= \Pr[f(x_1) \in S(y_1)]\Pr[f(x_2)\in S(y_2)] \\
&= \Pr[f'(x_1)=y_1]\Pr[f'(x_2)=y_2]
\end{align*}
より主張が得られます. (証明終)
補題2,3を組み合わせると, 以下の命題が成り立つことがわかります.
補題4.
任意の$m\le n$に対し, $\{0,1\}^n$から$\{0,1\}^m$へのペア独立ハッシュ関数$f$であって, 全ての$x\in\{0,1\}^n$に対して$f(x)$の分布が$\{0,1\}^m$上一様ランダムになるようなものが存在する. さらに$x\mapsto f(x)$の計算は$\mathrm{poly}(n)$時間で計算できる.
Valiant--Vaziraniの定理の証明
いよいよ定理1を証明します. $\phi\colon\{0,1\}^n\to\{0,1\}$を与えられた論理関数とし, 以下の帰着を考えます:
- $m\sim\{1,\dots,n\}$を一様ランダムに選ぶ.
- $f\colon\{0,1\}^n\to\{0,1\}^m$を補題4で保証されるペア独立ハッシュとする.
- $\phi'(x)=\phi(x)\land \langle f(x)=1^m\rangle$で定義される論理関数$\phi'$を出力する.
ステップ3では, Cook-Levinの定理の証明からコンピュータで計算できるアルゴリズムはその内部(レジスタや読み込みテープの位置など)の動きを回路で表現できることを用います. すなわち, 補題4では$x\mapsto f(x)$は多項式時間で計算できるので, この計算を回路で表現することによってBoolean関数$x\mapsto \langle f(x)=1^m\rangle$を$n$に関する多項式サイズの回路で表現することができます (SATを考えると, このようにペア独立ハッシュ関数の計算過程を表現できるというuniversalityが役にたつというわけです!). 従って$\phi\mapsto \phi'$を計算する上記の乱択アルゴリズムは多項式時間アルゴリズムです.
正当性の証明
$\phi'$の正当性を証明します. 与えられた論理関数$\phi$が充足不可能ならば$\phi'$を充足する割当も存在しません. 従って$\phi$が充足可能であるときに$\phi'$が充足可能である確率を評価すればよいです.
$\phi$が充足可能であるとし, $1\le N \le 2^n$を$\phi$の充足割当の個数とします. 充足割当が非常に多く, 例えば$N\ge 2^{n-3}$を満たすならば一様ランダムな$x\sim\{0,1\}^n$に対して$\phi(x)=1$かどうかをチェックすれば$\phi$の充足可能性が簡単に解けて, $\phi$が充足可能ならば定数$1$を$\phi'$として出力すればよいので, $N\le 2^{n-3}$を仮定します.
$m\sim[n]$が一様ランダムに選ばれているので, 確率$1/n$で
\begin{align}
2^{m-3}\le N \le 2^{m-2}
\end{align}
を満たします. 以後は$m$が(1)を満たすと仮定して議論を進めます.
$\phi$の充足割当の全体を$a_1,\dots,a_N$ ($a_i\in\{0,1\}^n$) とし, 確率変数$X_i=\langle f(a_i)=1^m \rangle$を考えると, $X=\sum_{i\in[N]} X_i$は$\phi'$の充足割当の個数に等しいです. ですので $\Pr[X=1]\ge 1/\mathrm{poly}(n)$を示すのが目標です. $N$と$m$の関係(1)より, $1/8 \le \mathbb{E}[X] \le 1/4$です.
任意の$x\in\{0,1\}^n$に対して$\Pr[f(x)=1^m]=1/2^m$なので, $\mathbb{E}[X]=N/2^m$を満たします. 従って
\begin{align*}
\Pr[X=1] &= \Pr[\exists i,X_i=1\text{ and }\forall j\neq i,X_j=0] \\
&= \sum_i \Pr[X_i=1\text{ and }\forall j\neq i,X_j=0] \\
&= \sum_i \Pr[\forall j\neq i,X_j=0\,|\,X_i=1]\Pr[X_i=1] \\
&= \sum_i (1-\Pr[\exists j\neq i,X_j=1\,|\,X_i=1])\Pr[X_i=1] \\
&\ge \sum_i \Pr[X_i=1] (1-\sum_{j\neq i} \Pr[X_j=1\,|\,X_i=1]\Pr[X_i=1]) \\
&= \sum_{i}\Pr[X_i=1]-\sum_{i\neq j} \Pr[X_i=1]\Pr[X_j=1] & & \text{pairwise independence}\\
&\ge \mathbb{E}[X] - \mathbb{E}[X]^2 \\
&\ge \frac{1}{8} - \frac{1}{16} & & \text{(1)}\\
&\ge \frac{1}{16}
\end{align*}
を得ます. $m$が一様ランダムなので, (1)が成り立つ確率は$1/n$です. 従って, $\phi$が充足可能のときに$\phi'\in U_{\mathrm{yes}}$となる確率は少なくとも$\frac{1}{16n}$となります. (証明終)
グラフ問題に対するペア独立性の応用
Valiant--Vaziraniの定理はSATに対してペア独立な関数を制約に加えることによって解の個数を減らすという帰着でしたが, 似たようなアイデアに基づいてグラフ上の部分グラフ数え上げ問題に対して解の個数を減らす帰着を与えることができます (ただし帰着後の問題は元の問題とは違う問題になってしまう).
次の二つの問題を考えます:
- 与えられたグラフ$G=(V,E)$が三角形を含むかどうかを判定せよ ($\mathrm{TRI}$)
- 有限体$\mathbb{F}_q$に対し, 各辺$e\in E$が$\mathbb{F}_q$の元を重みとして持つ辺重みグラフ$\tilde{G}$を考え, 辺重みの総和が$0$になるような三角形（以後はゼロ三角形と呼ぶ) の存在性を判定せよ ($\mathrm{ZWT}_q$)
問題1は隣接行列の三乗を計算して対角成分を見ればよいので$O(n^{\omega})$時間で計算できます. 問題2は精緻な計算量 (fine-grained complexity) の文脈で難しい問題とされていて, $q$が十分大きいときは任意の定数$\varepsilon>0$に対して$O(n^{3-\varepsilon})$時間で解けないと予想されています. ですので, 本質的には$\mathrm{TRI}$と$\mathrm{ZWT}_q$の間にはギャップがありそうだと思われており, $\mathrm{ZWT}$の方が難しいと思われています.
ここで, 問題2においてゼロ三角形が高々一つであることを保証する問題を$\mathrm{UZWT}$とします. $q\approx 3\log n$のとき, $\mathrm{TRI}$から$\mathrm{UZWT}_q$への乱択帰着が存在します.
証明のアイデア. 与えられた$\mathrm{TRI}$のインスタンス$G=(V,E)$に対し, 各辺に$\mathbb{F}_q$上一様ランダムな重みを付与したグラフ$\tilde{G}=(V,\tilde{E})$を考えます. $G$の各三角形$(u,v,w)$に対し, この三角形が$\tilde{G}$においてゼロ三角形になる確率は$1/q^2$です. なので適当な範囲から$q$をランダムに選ぶと, ある程度の確率で$q^2$が$G$の三角形の個数と大体同じくらいになります. また, $G$の三角形$T$に対して$X_T$を三角形$T$が$\tilde{G}$においてゼロ三角形になるかどうかの指示関数とすると, $(X_T)_T$はペア独立になります！
この事実を確認するために, 相異なる二つの三角形$T\neq T'$を考えます. $T$と$T'$が辺を共有しない場合は$X_T$と$X_{T'}$は独立です. 仮にこの二つの三角形が辺を共有していたとしても, $T\neq T'$より共有している辺の本数は必ず$1$本になり, これ以外の辺の重みは独立に決まるので$X_T$と$X_{T'}$は独立になります.
従って, ランダムに重みを付与したZWTのインスタンス$\tilde{G}$はある程度の確率でゼロ三角形を唯一含みます.
