2月に冬のLAに参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました.
2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。
— Nobutaka Shimizu (@knewknowl) December 22, 2023
自分の発表には全く関係ないことですが, 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です. どちらも非常に偉大な方です. 原著論文はこちらです.
- $\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}}$.
仮にUSATが多項式時間アルゴリズム$A$で解けたとしましょう. このアルゴリズム$A$を定理1のアルゴリズム$R$と組み合わせることで以下のようにしてSATを解くことができます:
- 与えられた論理関数$\phi$を入力として$R$を走らせ, 別の論理関数$\phi'$を得る.
- $\phi'$を入力として$A$を走らせ, YESを出力したらそのままYESを出力する.
- そうでなければステップ1に戻る. これを$100p(n)$回繰り返しても終わらない場合はNOを出力する.
証明のアイデア
- $\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$の指示関数とする.
ペア独立性
\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)であると言うこともあります.
\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$ビット文字列への関数とみなせます.
証明. 任意の$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$にしつつペア独立になるようにできます.
証明. 確率変数$(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を組み合わせると, 以下の命題が成り立つことがわかります.
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$)
この事実を確認するために, 相異なる二つの三角形$T\neq T'$を考えます. $T$と$T'$が辺を共有しない場合は$X_T$と$X_{T'}$は独立です. 仮にこの二つの三角形が辺を共有していたとしても, $T\neq T'$より共有している辺の本数は必ず$1$本になり, これ以外の辺の重みは独立に決まるので$X_T$と$X_{T'}$は独立になります.
