講義資料を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$になるので検証者は拒否

となる。（証明終）

情報理論と加法的組合せ論の交差点: Changの不等式

概要

加法的組合せ論における基本的な定理の一つとして, Changの不等式と呼ばれるものがあります. これは, ベクトル空間 $\mathbb{F}_2^n$ の部分集合 $A\subseteq \mathbb{F}_2^n$ に対し, その指示関数の各フーリエ係数を見たとき, 絶対値の意味で大きい係数に対応するcharacter全体がなす部分空間の次元は小さいことを述べる定理です.

元々は複雑な議論を経て証明されていたのですが, Impagriazzoら(2014)によってエントロピーを用いた簡潔でとても賢い証明が与えられたので解説します. なお, 元論文やこの記事では$\mathbb{F}_2$を考えていますがより一般の有限体$\mathbb{F}_p$ ($p$が素数べき) でも, フーリエ解析の定義を変えるだけへ同様の議論で同じ結論が得られます.

エントロピーとは情報理論では主要な道具であり, 古典的にはシャノンの通信路符号化定理などが大学の講義でよく出てくるのですが, 近年は加法的組合せ論においてはMarton予想を解決したGowersら(2025)をきっかけに大きな注目を浴びています（その前からエントロピーを使った議論はいくつかありましたが）. この記事ではあまり加法的組合せ論には触れず, 単にChangの不等式とその証明にスポットをあてて解説していきます. 情報理論とフーリエ解析の交差点のように謳っていますが本質的にはPinskerの不等式とエントロピーの劣加法性しか使いません.

なお, この記事では簡単のため, 常に$\mathbb{F}_2^n$という空間にスポットをあてて議論していきますが, 加法的組合せ論の研究対象はこれに限らずアーベル群を考えることが多いです.

Changの不等式とは？

Changの不等式を述べるためにまず $\mathbb{F}_2^n$ 上の関数に対するフーリエ変換の定義を述べていきます. $\mathbb{F}_2^n$から$\mathbb{R}$への関数全体に対し,
\[
\langle f,g\rangle = \mathbb{E}_{x\sim \mathbb{F}_2^n} [f(x)g(x)]
\]
によって内積を定めます. ここで $x\sim \mathbb{F}_2^n$ とは, $\mathbb{F}_2^n$から一様ランダムに元 $x$ を選ぶ, ということを意味し, それに関する期待値をとっています. 以後, 期待値をとるときは常に一様分布を考えるので$\mathbb{E}_{x\sim\mathbb{F}_2^n}$を省略して$\mathbb{E}_x$と書くことにします.

次に, 各ベクトル $r\in\mathbb{F}_2^n$ に対し, 関数 $\chi_r\colon\mathbb{F}_2^n\to \{-1,1\}$を
\[
\chi_r(x) = (-1)^{\sum_{i=1}^n r_i x_i}
\]
と定めます. ここで右肩の総和は$\mathbb{F}_2$上の演算で考えています (mod 2をとらなくても$\chi_r(x)$の値は変わらないのでどちらでもよいです).

このとき, 任意の関数 $f \colon \mathbb{F}_2^n\to\mathbb{R}$は以下のように線形結合で表すことができます:
\[
f(x) = \sum_{r\in\mathbb{F}_2^n} \langle f, \chi_r \rangle \cdot \chi_r(x).
\]
これをフーリエ逆変換と呼びます. つまり, $(\chi_r)_{r\in\mathbb{F}_2^n}$は, 関数全体の空間$\{f\colon \mathbb{F}_2^n\to\mathbb{R}\}$を線形空間とみなしたときの直交基底のように扱うことができるわけです. このときの線形結合の各係数を
\[
\widehat{f}(r) := \langle f, \chi_r \rangle = \mathbb{E}_x[f(x)\cdot (-1)^{\sum_{i=1}^n r_ix_i}]
\]
と表します.

以下にフーリエ級数に関する基本的な事実を述べていきます：

• $\langle f,f\rangle = \mathbb{E}_x [f(x)^2] = \langle \widehat{f},\widehat{f} \rangle = \mathbb{E}_r[\widehat{f}(r)^2].$ (Parsevalの等式). より一般に写像 $f\mapsto \widehat{f}$ は線形変換であり, ユニタリである.
• 定義から簡単に確認できるが, $\widehat{f}(0)=\mathbb{E}_x[f(x)]$.

加法的組合せ論は極値組合せ論と少し似ていて, 集合$A\subseteq\mathbb{F}_2^n$が密である時にそれが何かしらの構造的性質を持つことを論ずる理論です (一般に$\mathbb{F}_2^n$に限らず一般のアーベル群を考えます）. 構造的性質とは「($\mathbb{Z}/n\mathbb{Z}$の場合は)長い等差数列を含む」だとか「次元の大きな部分空間を含む」といった類の性質です. 

そこで集合$A\subseteq \mathbb{F}_2^n$ を指示関数 $A\colon \mathbb{F}_2^n\to\{0,1\}$と同一視します. この集合$A$の密度を$\delta(A):=|A|/2^n$ で定めます. 

一般にベクトル $a=(a_1,\dots,a_n)\in\mathbb{R}^n$ に対して, 絶対値の大きな成分があると, そのインデックスはベクトル$a$の特徴を掴んでいるといえます. この発想をフーリエ変換にも持ち込みましょう. 関数 $A$ を基底 $(\chi_r)_r$ の線型結合で表したとき, $|\widehat{f}(A)|$が大きいような $r$ を集めると, それが $A$ の構造的な性質を反映しているように思えます. Changの不等式とは, そのような $r$ の全体は実は小さな部分空間に収まっていることを述べる定理です.

正確に述べるために, パラメータ $\rho>0$ に対して
\[
\mathrm{Spec}_\rho(A) := \{r\in \mathbb{F}_2^n\colon |\widehat{A}(r)|>\rho\cdot\delta(A)\}
\]
と定めます (ここでの不等号は真の不等号$>$になっていることに注意).

定理1 (Changの不等式).

任意の集合 $A\subseteq\mathbb{F}_2^n$ および パラメータ $\rho>0$ に対し, $\mathrm{Spec}_\rho(A)$ は高々 $\rho^{-2}\log(1/\delta(A))$ 本の線形独立なベクトルを含む. すなわち

\[
\dim \mathrm{span}(\mathrm{Spec}_\rho(A)) \le \frac{2\log(1/\delta(A))}{\rho^2}.
\]
(ここで$\log$は自然対数).

証明の準備 (エントロピー)

Changの定理の証明をするために, エントロピーの概念や基礎事項を導入します. 有限集合 $\Omega$ 上に値をとる確率変数 $X$ のエントロピー $H(X)$ を
\[
H(X) := \sum_{x\in\mathsf{supp}(X)} \log\frac{1}{\Pr[X=x]}
\]
で定めます. ここで$\mathsf{supp}(X)=\{x\in\Omega\colon\Pr[X=x]>0\}$は確率変数 $X$ の台です. なお, 情報理論ではしばし$\log$の底は2にしますが, ここでは自然対数を考えます (本質的にはどちらでも良いのですが, 自然対数の方が後で紹介するPinskerの不等式の見栄えが良くなります）.

ここではベクトル空間$\mathbb{F}_2^n$上に値をとる確率変数$X=(X_1,\dots,X_n)$を考えていくことになりますが, このようなベクトル値をとる確率変数のエントロピーについては以下の重要な不等式が成り立ちます：

補題2 (エントロピーの劣加法性). 

$X=(X_1,\dots,X_n)$を$\Omega^n$上に値をとる確率変数とする (ただし$\Omega$は有限集合). このとき

\[
H(X) \le H(X_1)+\dots+H(X_n).
\]

例えば$X$が$\mathbb{F}_2^n$上で一様ランダムに選ばれたとしましょう. このときは$X_1,\dots,X_n$はそれぞれ独立に$\mathbb{F}_2^n$上で一様に分布するため,
\begin{align*}
&H(X)=n\log 2,\\
&H(X_i)=\log 2
\end{align*}
となり, 補題2を等式で満たします.

次に, Pinskerの不等式と呼ばれる基礎的な不等式を導入します. 同じ有限集合$\Omega$上に値をとる二つの確率変数 $X,Y$ に対して
\[
d_{TV}(X,Y) = \frac{1}{2}\sum_{x\in\Omega}|\Pr[X=x]-\Pr[Y=x]|
\]
を全変動距離 (total variation distance) と呼びます. 分布をベクトルとみなしたときのいわゆる$\ell_1$ノルムに相当する距離です.

一般に確率変数のエントロピー $H(X)$ とは $X$ が「どれほどのランダムネスを含むか」を示す指標ですが, 直感的にはこれが大きいほど$X$の分布は一様分布に近いことが予想されます. Pinskerの不等式（のエントロピーに対する特殊ケース）は, 確率変数のエントロピーと一様分布からの全変動距離の大きさの関係を表す不等式です.

補題3 (Pinskerの不等式の特殊ケース).

有限集合$\Omega$上に値をとる確率変数$X$を考え, $\Omega$上の一様分布に従う確率変数を$U$とする. このとき

\[
\log|\Omega| - H(X) \ge 2d_{TV}(X,U)^2.
\]
ただし$\log$は自然対数.

本来のPinskerの不等式では左辺はより一般の二つの確率変数$X$と$U$のKLダイバージェンス $\mathrm{KL}(X||U)$と呼ばれる量になるのですが, $U$が一様分布のとき$\mathrm{KL}(X||U)=\log|\Omega| - H(X)$という等式が成り立つことを利用しました. 

Changの不等式の証明

ここまででChangの不等式の証明の準備ができました. 以下の重要な補題を証明します.

補題4.

集合 $A\subseteq\mathbb{F}_2^n$ に対し, $\alpha=\delta(A)=|A|/2^n$とする. ベクトル$e_1,\dots,e_n\in\mathbb{F}_2^n$を単位ベクトルとする (つまり, $e_i$は第$i$成分が$1$で他の成分は全て$0$). このとき

\[
\sum_{i=1}^n \widehat{A}(e_i)^2 \le 2\alpha^2\log(1/\alpha).
\]

注釈. 実際には$e_1,\dots,e_n$として, $\mathbb{F}_2^n$の任意の基底をとっても同じ主張が成り立つことが定義から簡単に確認できます（一般の基底を考えても標準基底$e_1,\dots,e_n$のケースに帰着できる).

証明. 集合$A$上一様ランダムに選ばれたベクトルを確率変数として $X=(X_1,\dots,X_n)$とします. このとき, $H(X)=\log |A| = \log \alpha 2^n = n\log 2 - \log(1/\alpha)$ が成り立ちます.

フーリエ級数の定義より
$$\begin{align*}
\widehat{A}(e_i) &= \mathbb{E}_{x}\left[ A(x) \cdot \chi_{e_i}(x) \right] \\
&= \mathbb{E}_{x}\left[ A(x) \cdot (-1)^{x_i} \right] \\
&= \frac{|A|}{2^n}\cdot \frac{1}{|A|} \sum_{x\in A} (-1)^{x_i} \\
&= \alpha\cdot \left(\Pr[X_i=0] - \Pr[X_i=1]\right).
\end{align*}$$
ここで, 一般に$\{0,1\}$上に値をとる確率変数 $Y$ に対して, $\{0,1\}$上一様分布に従う確率変数を$U$とすると,
$$\begin{align*}
d_{TV}(Y,U) &= \frac{1}{2}|\Pr[Y=0]-1/2| + \frac{1}{2} |\Pr[Y=1]- 1/2| \\
&= |\Pr[Y=0]-1/2| \\
&= \frac{1}{2}|2\Pr[Y=0] - 1 | \\
&= \frac{1}{2} |\Pr[Y=0] - \Pr[Y=1]|
\end{align*}$$
が成り立つことから,
$$\begin{align*}
\widehat{A}(e_i)^2 = \alpha^2 \cdot 4d_{TV}(X_i,U)^2 \le 2\alpha^2 \cdot (\log 2 - H(X_i))
\end{align*}$$
を得ます (最後の不等式でPinskerの不等式を用いた). これを全ての$i$について足し合わせてエントロピーの劣加法性を用いると
$$\begin{align*}
\sum_i \widehat{A}(e_i)^2 &\le 2\alpha^2 n \log 2 - 2\alpha^2 \sum_i H(X_i) \\
&\le 2\alpha^2 n\log 2 - 2\alpha^2 H(X) \\
&= 2\alpha^2 n\log 2 - 2\alpha^2 (n\log 2 - \log(1/\alpha) \\
&= 2\alpha^2\log(1/\alpha)
\end{align*}$$
となり, 主張を得ます. (証明終)

この補題は$\mathbb{F}_2^n$の標準基底 $e_1,\dots,e_n$ におけるフーリエ級数の二乗和を抑えるものでしたが, 一般の基底 $b_1,\dots,b_n$ に対しても同様に成り立ちます:

系5.

集合 $A\subseteq\mathbb{F}_2^n$ に対し, $\alpha=\delta(A)=|A|/2^n$とする. 線形独立な$n$個のベクトル $b_1,\dots,b_n\in\mathbb{F}_2^n$ に対して

\[
\sum_{i=1}^n \widehat{A}(b_i)^2 \le 2\alpha^2\log(1/\alpha).
\]

証明. 適当な正則行列 $B$ を用いて $b_i^\top B = e_i^\top$ が成り立つようにできます. 集合 $B\cdot A$を $B\cdot A = \{Bx \colon x\in A\}$ とすると
$$\begin{align*}
\widehat{A}(b_i) &= \mathbb{E}_x\left[ A(x) \cdot (-1)^{b_i^\top x} \right] \\
&= \mathbb{E}_x\left[ A(x) \cdot (-1)^{e_i^\top B x} \right]  \\
&= \mathbb{E}_y\left[ A(B^{-1} y) \cdot (-1)^{e_i^\top y} \right]  & & y=Bx\\
&= \mathbb{E}_y\left[ B\cdot A(y) \cdot (-1)^{e_i^\top y} \right] \\
&= \widehat{B\cdot A}(e_i).
\end{align*}$$

また, $|B\cdot A|=|A|$なので, 補題4を集合$B\cdot A$に適用すれば得られます. (証明終)

いよいよ Chang の不等式の証明の準備ができました.

定理1の証明. 集合$A\subseteq \mathbb{F}_2^n$に対し, 集合 $\mathrm{Spec}_{\rho}(A)$ が $d:=\frac{\log(1/\delta(A))}{\rho^2}$ 本の線形独立なベクトル $b_1,\dots,b_d \in\mathbb{F}_2^n$ を含むとします. これらのベクトルを含む基底 $b_1,\dots,b_d,b_{d+1},\dots,b_n$ を選びます.

この基底に対して系5を適用すると
$$\begin{align*}
\sum_{i=1}^n \widehat{A}(b_i)^2 \le 2\delta(A)^2 \log(1/\alpha).
\end{align*}$$
一方で, $b_1,\dots,b_d\in\mathrm{Spec}_\rho(A)$なので
$$\begin{align*}
\sum_{i=1}^d \widehat{A}(b_i)^2 \ge \rho^2\delta(A)^2\cdot d
\end{align*}$$
が成り立つので, $d \le \frac{2\log(1/\alpha)}{\delta(A)^2}$ が成り立ちます.

アルゴリズムの理論研究の最高峰とは?

競プロで道具として用いられる様々な賢いアルゴリズムやデータ構造の多くは, 非常に賢い研究者たちによって発見されており, ほとんどは理論計算機科学の論文として国際学会の会議録や学術雑誌の形として出版されています. ここではアルゴリズム系の研究論文がよく出てくる様々な国際会議を紹介します. ちなみに各国際会議は基本的に年1回の頻度で開催され, そのために我々研究者はがんばって研究して論文を締め切り前に間に合わせるという「論文執筆マラソン」をしています. ちなみに以下の説明では「(会議名)に論文を通す」という言い方をしますが, これはその会議に論文が採択されるということを意味します.

以下に重要な注意事項を書き添えておきます:

• 国際会議は基本的に複数人(大体3人くらい)による査読の評価によって採択の可否が決定されます. 一般に査読の期間は1ヶ月程度であることが多いため, 細かい証明の隅々まで読まれることは稀です. そして査読者がその論文の文脈のエキスパートであることもあれば, そうではない可能性もあります. 従って, 運良くエキスパートに査読を引き受けてもらえた場合は精度の高い評価を下されることが期待されますが, そうではない可能性もそれなりに大きく, その時は正当な評価が下されない可能性もあります (そもそも証明が間違っているけど見逃されて通る可能性だってあります). ですので, 採択の可否にはある程度の運要素が絡んでくることもあることを念頭においてください (こうならないよう, 論文では誰にとっても分かりやすく背景やその手法の凄さをアピールするなどの工夫を凝らす必要があるのです). 
• 凄い会議に論文を通すことは誉れの一つではあるものの, それが凄さの指標の全てでは決してありません. 大学の運営業務や講義などの間の時間を縫って, 学会やシンポジウムの運営, 本の執筆, 研究予算を獲得し学生の旅費を捻出して学生を育成するなど, 様々な形で分野に多大な貢献をしている先生は多くいらっしゃいます. あなたが学生であるならば, あなたの指導教員はマジでめちゃくちゃ凄い人です. ぜひ仲良くしましょう. ついでに将来偉くなる可能性があるので私とも仲良くしましょう.
• 以下では非常にレベルの高い国際会議を紹介して「めちゃくちゃすごい」と言っているだけですが, 私個人の意見としてはこれらを過度に神格化せず, 実は「意外と手の届くところにある」という認識を持って臆せずチャレンジし続けるべきだと思います.

1.Symposium on Theory of Computing (STOC)

理論計算機科学で最もレベルが高い国際会議は二つあり, そのうちの一つがSTOCという国際会議です. 例えばNP完全性の概念を導入したCook (1971)はSTOCの論文です. STOCのスコープは理論計算機科学全般であり, 例えばSTOC2025のcall for paperには

Papers presenting new and original research on the theory of computation are sought. Typical but not exclusive topics of interest include algorithms and data structures, computational complexity, randomness in computing, algorithmic graph theory and combinatorics, analysis of Boolean functions, approximation algorithms, cryptography, computational learning theory, continuous and discrete optimization, economics and computation, parallel and distributed algorithms, quantum computing, algorithmic coding theory, computational geometry and topology, computational applications of logic, algebraic computation, and computational and foundational aspects of areas such as machine learning, fairness, privacy, networks, data management, databases and computational biology. Papers that extend the reach of the theory of computing, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged. The program committee will make every effort to consider a broad range of areas. The program committee will make every effort to consider a broad range of areas.

とあります. STOCに採択されるためには凄い証明を使って強い結果を示しつつ, その結果の背景とインパクトをアピールし, さらにその証明アイデアをめちゃくちゃ分かりやすく説明するなど, 非常に多大な努力を伴います. そのため, STOCに採択されることは理論計算機科学の研究者にとって最も栄誉なことであると同時に, 何度もSTOCに通している人はその研究トピックに関する世界的なエキスパートの一人であると認識されていきます.

ちなみに自分が2024年に参加したときは賢いアルゴリズムを提案する論文よりも計算量下界を導出した論文の方が採択される率は高いということを運営の方が発表していました.

2. Symposium on Foundations of Computer Science (FOCS)

先ほど述べた「理論計算機科学で最もレベルが高い国際会議」の二つのうちのもう一つがFOCSという国際会議です. 内容的には基本的にSTOCと同じなのですが, 違いはスポンサーにあり, STOCはACM SIGACTによってサポートされていて, FOCSはIEEEによってサポートされています. FOCS2025のcall for paperはSTOC2025とほぼ同じです:

Papers presenting new and original research on theory of computation are sought. Typical but not exclusive topics of interest include: algorithmic coding theory, algebraic computation, algorithmic graph theory, algorithmic game theory, algorithms and data structures, analysis of Boolean functions, approximation algorithms, average-case complexity, computational applications of logic, combinatorics, computational complexity, communication complexity, circuit complexity, combinatorial optimization, computational game theory, computational geometry, computational learning theory, continuous optimization, cryptography, foundations of machine learning, online algorithms, optimization, parallel and distributed algorithms, parameterized algorithms, randomized algorithms, sublinear algorithms, streaming algorithms, quantum computing, pseudorandomness and derandomization, foundations of fairness and privacy, and theoretical aspects of areas such as networks, information retrieval, computational biology, and databases. Papers that broaden the reach of the theory of computing, or raise important problems that can benefit from theoretical investigation and analysis, are encouraged.

STOCとFOCSはどちらもほぼ同程度にレベルが高く, その採択は非常に誉高い業績とされています. ちなみにアルゴリズム系と一口にいってもSTOCやFOCSでは暗号や量子計算の話もよく出てきます.

3. Symposium on Discrete Algorithms (SODA)

SODAはSTOC/FOCSと比較するとややレベルは落ちるものの, それでもなお非常にレベルの高い国際会議です. タイトルにあるように離散アルゴリズムに関する国際会議ですが, 実際のところはグラフといった離散構造の論文や計算量下界の論文もあるので, まぁなんでもありの会議です (例えば自分はアルゴリズムが全く出てこない論文を通したことがあります).

SODA, STOC, FOCSの三つはまとめて理論系のトップ会議として言及されることが多々あります.

• 理工学部教授 浅野孝夫 最終講義「離散アルゴリズムと国際会議STOC・FOCS・SODAとの出会いから」を開催
• 理論系(STOC, FOCS, SODA)からビッグデータ・AIのトップ会議へ
• JST ERATO巨大グラフプロジェクト２０１２－２０１７ 総括と遺言
• 河原林健一氏の日本学士院学術奨励賞受賞に寄せて

特に三つ目のスライド資料はとても面白いのでぜひ眺めてみてください. 河原林先生のSTOC, FOCSへの情熱が感じられます. また, 四つ目のリンクでは, 徳山 豪 先生は「日本人研究者では，生涯に 1 つ論文が載ればかなり優秀で，複数の論文を持つ研究者は数えるほどしかいない．」と述べています.

なお, アメリカとかだと凄い先生の下で一緒に論文を書いてたくさんSODA, STOC, FOCSに論文を通すという学生は結構いるのですが, 残念ながら日本では(大学教員の多忙さも相まって)そのレベルの研究をコンスタントに実行できる凄い先生がほとんどいないこともあり, 日本でSODAに論文を通す学生は2,3年に一人いるかどうか, STOC/FOCSに通す学生は5,6年に一人いるかどうかだと(個人的な感覚ですが)思っています. ちなみにSODA, STOC, FOCSにはたまに競プロの凄い人も発表していることがあり, Google Code JamのTシャツとかを着てる人を何回か見かけたことがあります.

他の会議

なお, 他にも理論計算機科学の分野の国際会議は非常にたくさんあります. 自分がすぐ思いつくだけでもICALP, ESA, CRYPT, SoCG, PODC, DISC, QIP, MFCS, CCC, SOSA, RANDOM, APPROX, WALCOM, ISAAC, ISSAC, STACS, IPCO, SPIRE, SAT, IPECなどがあります (他にももっとあります. メジャーなもので抜けてるものがあったら追加するので教えてください).

SODA, STOC, FOCSが別格というだけでこれらの中にもとてもレベルの高い国際会議はいくつかあります. 例えばPODC (Symposium on Principles of Distributed Computing) は分散計算にフォーカスを絞った国際会議で, CCC(Computational Complexity Conference)は計算量下界に関する国際会議です (いずれもレベルの高い会議として認識されています). 個人的にはランダムネスに関する会議RANDOMが好きです. トピックが絞られているが故の利点もいくつかあります:

• 自分の専門に近い査読者に査読がいきやすい
• 参加するとそのコミュニティと繋がりやすい
• そもそも自分の専門分野に近いので面白い発表が多い

また, 他にもアルゴリズム全般を扱う汎用的な国際会議はICALP (Track A), ESA, MFCS, WALCOM, ISAACなどがあり, 学生の国際学会発表の経験を積むという点でも非常に重要な役割を果たします. 人によって色々ありますが, 私の認識ではこれらの中ではICALP (Track A)が頭一つ抜けているイメージです (他の会議はどんな感じなのか本当に何も知らないので何かご存知のことがあったらXかリアルで会ったときに是非教えてください). これらの中にも歴史的な論文は多くあります. 例えば行列積の検算を乱択で行うFreivaldsのアルゴリズムはMFCS(1979)に採択された論文に登場しています).

なお, 全ての国際会議に共通して言えることですが, 論文の採択可否の決定や現地での運営など, 非常に多くの人の多大な協力によって開催されています. 国際会議に参加する際は, その裏にはそういった努力があることをぜひ念頭において, 楽しみましょう!

ざっくり解説: 焼きなまし法はなぜうまくいくのか？

概要

焼きなまし法は遺伝的アルゴリズムなどと並ぶ最適化問題の発見的解法の一つとして有名であり, 競技プログラミングの文脈ではマラソン(厳密解を求めるのが困難とされる一つの最適化問題に長時間取り組み最も最適値に近い解を得るという種目) においては常套手段の一つとして用いられています. 従ってこの文脈では様々な解説記事があるのですが, いわゆるマラソン競技特有の「コツ」や実装方法の説明がほとんどで, 焼きなまし法自体を数理的に深掘りした記事もなくはないのですが, やはり「なぜうまくいくのか」の観点で説明している記事はほとんど見たことがないので, なんとなくこの辺りが気になるという人向けにこの記事で解説していきます (公開時は把握してなかったのですが, 本記事の内容はこちらの記事とほぼ同じ内容になっていますので, 数理的な説明をする記事が全くないというわけではありません). 内容としてはメトロポリス・ヘイスティング法の説明になりますが, 数学的な厳密性は犠牲にして自分の理解で執筆していますので, 厳密な議論まで気になる方は論文を読んでください (もしかしたら他の説明の仕方があるかもしれません).

結論から述べると

• 焼きなまし法は, 遷移確率が時間とともに変動するランダムウォークを実用的な観点から修正したものとみなすことができる.
• このランダムウォークは, 遷移確率の変動が各時刻において十分に微小であれば, そのランダムウォークの収束先は最適解上の分布になることが保証される.
• しかし, 理論的に保証される収束は非常に遅いため, 実用の場面では, 適当なところでランダムウォークを打ち切ったり, より良い解を得るための(理論保証のない)修正を施す. これがマラソンなどの場面でよく見かける焼きなまし法である.

この記事にアクセスする人は焼きなまし法についてはなんとなく知ってるということを仮定します. ただ, 念の為, 初見の人にもアクセスできるよう, 焼きなまし法に関する説明を次の章で与えておきます. 焼きなまし法を知っている人はその次の2章までスキップして構いません.

1. 焼きなまし法とは?

焼きなまし法とは最適化問題に対し, 最適に近いであろう実行可能解を得る手法の一つで, 局所探索と呼ばれるカテゴリーに属します. 局所探索とは, 何かしらの実行可能解を一つ用意し, その解を逐次更新していくというアルゴリズムの総称であり, 焼きなまし法以外には山登り法などが知られています. ここでは以下の記法を用います.

• 実行可能解全体の空間は有限集合とし記号$S$で表します. 
• 実行可能解を$x,y,z\in S$などと表します
• 目的関数値を$f\colon S \to \mathbb{R}_{\ge 0}$で表し, 最小化を目指すこととします.
• 実行可能解$x\in S$の近傍集合を$N(x) \subseteq S$とし, その要素$y\in N(x)$を近傍と呼ぶ.

すなわち, $S$という有限集合と$S$上に非負値をとる関数$f$があり, $f(x)$が最小となる$x\in S$を見つけることが目的となります. 直感的には近傍$y \in N(x)$は$x$と「ちょっとだけ違う実行可能解」です. 実行可能解と目的関数の定義は考える最適化問題に依存しますが, 実行可能解はアルゴリズムの設計者が定義するため, 同じ最適化問題であっても様々な近傍を考えることができます.

山登り法では, 現在の実行可能解$x\in S$に対し, $f(y)$が最小となる近傍$y\in N(x)$を選び, それを$x$に置き換えて同じ処理を繰り返すというアルゴリズムです (または$N(x)$の元$y$を順番に一つずつ見ていき, $f(x)>f(y)$を満たす近傍$y$が見つかったらその瞬間に$x:=y$とするようなものも考えられる. これは, $|N(x)|$の要素数が非常に大きい時は$\min_{y\in N(x)} f(y)$を計算に時間がかかる際に有効な方法である).

このアルゴリズムだと谷底 (全ての近傍の目的関数値が今の解より真に良くならないような解; 局所最適解と呼ぶ) にいきつくとそれ以上動かなくなるのでアルゴリズムは終了します. 上図の例では偶然にも最適解に辿り着きますが, 一般に谷底は複数あり, どの谷底に至るかは一番最初に選んだ解に依存するため, 最適性の保証はありません (ただし空間が連続的で目的関数値が凸性を持つなど, 特定の状況下では最適性が保証できます).

一方, 焼きなまし法では, 現在の実行可能解$x\in S$に対し, 近傍$y\in N(x)$を順番に見ていき,

1. 目的関数値が改善, すなわち$f(x)>f(y)$を満たすとき, $x:=y$として次の反復へ移行
2. そうでない場合, $f(x),f(y)\in\mathbb{R}_{\ge 0}$, そしてこれまでの反復回数$t$のみから定まるある確率$p$で$x:=y$として次の反復へ移行

というアルゴリズムです. 例えば$p=0$ならば山登り法に一致します.

焼きなまし法では確率的に登ることがある.

ここで確率$p$は

$$ p = \exp\left(-\frac{f(y) - f(x)}{T}\right) \tag{1} $$

とします. ここで$T=T(t)>0$は温度と呼ばれるパラメータであり, これまでの反復回数$t$の関数であり, $t\to\infty$としたとき$T\to 0$となります. ここで, $f(y)\ge f(x)$を仮定しているため常に$p\in[0,1]$です.

確率$p$については以下の観察ができます:

• 解の改悪幅$f(y)-f(x)$が大きいほど$p$が小さい, すなわち$x\to y$の遷移が発生しにくい.
• 改悪幅を正の値で固定したとき, 温度$T$が$0$に近いほど$p$は小さくなります. つまり, $T$が大きいときは改悪($f(x)<f(y)$なる$y\in N(x)$への更新)が発生しやすくなるが, 反復を繰り返し$t\to\infty$としていくと$T\to 0$に近づくため, より山登り法に近い振る舞いをするようになる.

温度$T(t)$の定め方は「非常にゆっくり$T\to 0$に収束する関数」であることが理想ですが, 実際に焼きなまし法を走らせる際は手っ取り早く良い解を得たい場合がほとんどなので, あらかじめ反復回数を決定しておき, 最終的に$T\approx 0$になるように線形で下がっていくようなものを考えることもあります. ただし理論的な保証があるのは「非常にゆっくり」収束するという条件が必要なので, この時点で理論保証から外れてしまうことになります.

2. メトロポリス-ヘイスティング法

突然ですが, 有限集合$S$上の関数

$$ f\colon S \to \mathbb{R}_{\ge 0} $$

が定まっているとき, $f(x)$を最小にする$x\in S$を求めるにはどうすれば良いでしょうか? 唐突ですが, 温度と呼ばれるパラメータ$T>0$に対して$S$上の確率分布$\pi\in[0,1]^S$を以下で定めます:

$$ \pi (x) = \frac{\exp(- f(x)/T)}{Z}. \tag{2}$$

ここで$Z = \sum_{x\in S}\exp(-f(x)/T)$は$\pi$を分布に正規化する値 (様々な文脈で分配関数と呼ばれる値) です. また, この分布$\pi$を(エネルギー$f$に対する)ボルツマン分布と呼ぶらしいです.

分布$\pi$に従って生成される確率変数$X \sim \pi$を考えると, 以下の観察が芽生えます:

• 温度$T$が非常に大きい値, 極端に言えば$T=\infty$ のとき, $f(x)$の影響は無視されるため, $\pi$は$S$上で一様ランダムとなります.
• 温度$T$が非常に小さい値, すなわち$T\approx 0$ のとき, $\pi$は最適解$S^*=\{x\in S\colon f(x) = \min_{y\in S}f(y)\}$上の一様分布となります.

従って, 理想的には$T\approx 0$において$\pi$に従う確率変数を生成できれば最適化問題を解いたことになります!! ところが, 分配関数$Z$が簡単に計算できそうな見た目をしてないので, $\pi$に従う確率変数をサンプリングするということ自体が非自明なタスクになっています. メトロポリス-ヘイスティング法とは, 目標となる分布$\mu$があったとき, ランダムウォークを用いてこの分布に非常に近い分布に従う確率変数を生成する手法の一つです.

具体的には, $S$上の何らかのランダムウォークの遷移確率行列$P \in [0,1]^{S\times S}$が与えられているとします. ここで$P(x,y)$は$x$から$y$に遷移する確率を表しており, 例えば焼きなまし法の例でいうと, 一様ランダムな近傍に遷移する, というランダムウォークだと思えばOKです. 一般にランダムウォークはその遷移がとある条件 (例えば遷移の強連結性など) を満たせば, 定常分布と呼ばれるある分布に収束するという事実が知られています. 今考えているランダムウォーク$P$もその条件を満たしているとします. ただし$P$の定常分布は目標としている分布$\pi$とは異なっていることもあります.

メトロポリス-ヘイスティングス法のイメージ

メトロポリス-ヘイスティング法とは, 手元にあるランダムウォーク$P$に適当な重さの自己ループの追加などにより修正し, 目標分布$\pi$を定常分布とするような別のランダムウォーク$P'$をうまく定めるという手法です.

より詳細を述べると, 修正後のランダムウォーク$P'$は以下のような形をしています: ランダムウォーク$P$により, $x\to y$という遷移が発生したとき, 確率$a(x,y)$でその遷移を受理し実際に遷移し, 確率$1-a(x,y)$でその遷移を拒否し$x$にとどまる.

簡単のため$P(x,x)=0$とすると, $P'\in[0,1]^{S\times S}$の成分は

$$
P'(x,y) = \begin{cases}
P(x,y)\cdot a(x,y) & & \text{if }x\ne y,\\
1-\sum_{y} P(x,y)\cdot a(x,y) & & \text{otherwise}
\end{cases}
$$

となります. 肝心の受理確率$a(x,y)$の定め方ですが, $P'$が定常分布$\pi$を持つように, そして$a(x,y)$の値ができるだけ大きくなるように (自己ループの確率が少ない方が遷移する回数が多くなるため) 設計します. 詳細は省きますが釣り合い条件と呼ばれる条件から, $P'$は次の等式

$$ {}^{\forall} x,y\in S,\quad\pi(x) P'(x,y) = \pi(y) P'(y,x) $$

を満たしていなければなりません. これに$P'$の成分を代入すると

$$ \pi(x) a(x,y) P(x,y) = \pi(y) a(y,x) P(y,x) $$

となります. 

計算の簡単のため, $P$が対称行列だとしましょう. すると上の等式は$\pi(x)a(x,y) = \pi(y)a(y,x)$となります. ここで, できるだけ$a(\cdot,\cdot)$の値を大きくとると, 片方は$1$に設定できます. 従って

\begin{align*}
&a(x,y) = \min\left\{ \frac{\pi(y)}{\pi(x)},\,1\right\},\\
&a(y,x) = \min\left\{ \frac{\pi(x)}{\pi(y)},\,1\right\}
\end{align*}

を得ます. このようにして定まる受理確率$a(x,y)$は$\pi(x)$と$\pi(y)$の比のみに依存するという素晴らしい性質を持っています. 実際, $\pi$が(2)のような形になっているとき, その比は分配関数$Z$に依存せず,

$$ \frac{\pi(y)}{\pi(x)} = \exp\left( - \frac{f(y)-f(x)}{T} \right) $$

で簡単に計算できます. この値はまさに(1)で考えていた値と一致します. つまり, 焼きなまし方とは, メトロポリス-ヘイスティングス法の受理確率を模した確率的な遷移を許容する局所探索といえます.

なお, 実際の焼きなまし法では温度パラメータ$T$は遷移回数とともに変動します. 直感的にはこの変動は十分ゆっくりであれば局所的には$T$が固定された値とみなせるので解析できそうですが, この直感を厳密な形にするにはそれなりの苦労が必要のようです (例えばこの記事. この辺は私もまだわかっていない)

なお, メトロポリス-ヘイスティングス法で得られるランダムウォーク$P'$は, 収束先の定常分布が$\pi$であるということのみが保証されるため, その収束の速さについては何も保証がありません. しかし, 適当な仮定の下では何かしらの収束時間のバウンドを与えることは可能となります.

3. まとめ

冒頭にも述べましたが, 要するに

1. 最適化問題を解くというタスクをある目標分布に従うサンプリングに置き換える
2. このサンプリングタスクをメトロポリス-ヘイスティング法で解く
3. プロセス1,2の構造をできるだけ保ちつつ, 実用的に手っ取り早く良い解を得るための工夫を施して実装したものが焼きなまし法である

ということになります (もしもうちょっと深い理論の話があったら教えていただけると幸いです). 

なお, 最適化問題は$f$が凸性を持つときは「局所最適解は最適解の一つである」が成り立つため非常に解きやすくなるのですが, 同様に分布$\pi$は対数凹性を持つときはサンプリングしやすいという事実があるようです. 実際, $f$が凸のとき, 対応するボルツマン分布$\pi$は$\log \pi(x) = -\frac{f(x)}{T}$より, 対数凹性を持ちます.

講義資料をNotionで書いてみた

 プログラミング応用という名前の講義を受け持っており, そこで組合せ最適化のベーシックな話題とそのPythonでの実装を教えているのですが, 資料をNotionで書いてみました.

講義資料をNotionで公開しているのでアルゴリズムの基礎とかNP困難性とかを勉強したい人はどうぞ.https://t.co/49oRdTTHC8 pic.twitter.com/lU20ymalwy

— Nobutaka Shimizu (@knewknowl) November 26, 2024

ちなみに授業の内容としては, アルゴリズムを教えて演習課題として競技プログラミングのような問題を出題しています. 例えば無向グラフの四角形の有無を, 頂点数 $n$ に対して $O(n^2)$ 時間で判定せよという問題を難問枠で出題しています. これらの問題をipynbファイルで作成し, 学生には google colab などでPythonで実装してもらうという形をとっています. 見た目としてはこんな感じです:

多くの講義では, 各回のLaTeXで作成した講義資料を別々のpdfにして配布するというスタイルをとっています. しかしながらpdfだと

• 他のpdfファイルへのリンクが貼れない (全ての講義資料をまとめて作り, 各回ごとに分割して配布するというやり方もあるが, それだと最初に全て作るのがとても大変)
• この部分のように証明の表示/非表示の切り替えができない (長い証明は一旦読み飛ばし, 資料の大枠を最初に俯瞰したい場合が多々ある)
• アルゴリズムのデモを動画として表示できない
• なんとなくデザインがイケてない (おい)

といった点が個人的に気に入りませんでした. そこで

見た目も良い感じで個人的にはかなり気に入っているのですが, 資料作成を通じて感じたメリット/デメリットを連ねておきます. 講義資料作成の参考になればと思います.

Notionとは?

簡単に言うとイケてる資料をweb上で作成できるサービスです. 私は以前から勉強した内容や論文を書く時のメモに使っています. 実際に講義資料を見てもらえると分かりやすいと思います.

メリットとしては

1. 全体的にイケてる
2. 数式が簡単に埋め込める. LaTeXの記法がそのまま使えるし, \begin{align*}...\end{align*}とかもそのまま使える.
3. コールアウトと呼ばれる装飾を使えば, 定理などの主張を簡単に書ける
4. ブロック毎に文を管理しており, それぞれのブロックへのリンクが簡単に貼れるので, 「フォード・ファルカーソン法では実行時間が遅くなる例が存在したが...」といった文が書けます.
5. トグルというブロックを使うことで, この部分のように表示のオン/オフを切り替えることができる.
6. 図や動画がドラッグ＆ドロップで簡単に貼れる.
7. draw.ioからこんな感じで, 自信のPCに保存することなく直接ページに図を埋め込める

このように見ると非常に素晴らしい選択肢のように思えるのですが, 一方でいくつか考えなければならない点をかかえています:

1. そもそもNotionが落ちたら資料が見れなくなる
2. ネットに公開する必要があるので, 公開できない内容は書けない
3. LaTeXのnewcommandとかができない (個人的にこれはかなり痛い)
4. VSCodeで執筆できないのでスニペットとかが使えない (Notionページのビューワーはあるらしい)

講義資料を作る最初の1,2週間は特に気にならなかったのですが, ずっとやってると上記の3と4はかなり辛くなってきました.

あとやはりNotionは重いらしいので, GitHub Pages + Foam とかも試してみようかなと思っています.