木分解は茨の道

0. 概要

以前の記事に紹介したグラフマイナー定理の証明において非常に重要な役割を担うのが木分解 (tree decomposition) という概念です.

木分解に関しては, 色んなサイト (例えばここ) やグラフ理論の本で取り上げられているので, 本記事では木幅の下界の示し方を紹介します. 具体的には, 木幅は minmax の形で定式化できるのですが, その双対となる茨数を maxmin の形で導入し, 強双対性が成り立つことを紹介します.

(＊): 個人的にはtree decompositionのことを「木っぽく」分解するという気持ちから樹状分解と心の中で呼んでいるのですが, ほとんどの方は木分解と呼んでいるのでそれに倣います.

1. 準備

1.1. グラフの定義

グラフ $G=(V,E)$ は無向とし, $E\subseteq \binom{V}{2}$ とする. $G$の頂点集合と辺集合をそれぞれ $V(G)$, $E(G)$ で表す. グラフ $H$ が $G$ の部分グラフであるとは, $V(H)\subseteq V(G)$ かつ $E(H)\subseteq V(G)$ が成り立つことをいう.

1.2 木分解・木幅の定義

グラフ $G$ に対し, 次の性質を満たす組 $(T, \mathcal{V})$ を $G$の木分解と言います.
まず $T$ は木で, $\mathcal{V}=(V_t)_{t \in V(T)}$ は, $T$の頂点 $t$ で添え字付けられた$G$の部分頂点集合族です. そして

     1. $\bigcup_{t \in T} V_t = V(G)$.
     2. $G$ の各辺 $e=\{x, y\}$ に対し, $\{x,y\}\subseteq V_t$ なる $t\in T$が存在する.
     3. 任意の頂点 $v \in V(G)$ に対して, $T$の頂点部分集合 $\{t\in V(T):V_t\ni v\}$ が誘導する $T$ の部分グラフは連結である.

 具体例などはこのページにあるので, ご覧ください. 木分解の役立つ性質として, 以下が知られています:

Proposition1.
グラフ $G$ の木分解 $(T,\mathcal{V})$ を任意にとってくる. ある $t\in V(T)$ が存在して, $G-V_t$の各連結成分の頂点数は高々 $|V(G)|/2$となる.

Proposition 1に出てくる $V_t$のことをセパレータと呼んだりします. 木の場合はある頂点を取り除くと残った二つの連結成分のサイズを $n/2$ 以下にすることができますよね？それと同じ気分です. セパレータを使うと分割統治法とかが使えて良いアルゴリズムが設計しやすくなります.

上: 木分解のセパレータ     下:木のセパレータ

定義2 (木幅)
グラフ $G$ の 木幅 $\mathrm{tw}(G)$ は,
$$\mathrm{tw}(G) = \min_{(T,\mathcal{V})}\max_{t\in V(T)} |V_t| - 1.$$

コメント.
木幅の定義式の $\min$ は$G$の全ての木分解をとります. よく知られるように, $G$が木である iff $\mathrm{tw}(G)=1$ となっており, $\mathrm{tw}(G)$ は $G$ の木っぽさを表す尺度になっています. 定義式の最後の -1 は本質的ではなく, 単に「木の木幅は1である」が成り立つようにするために導入されてるのだと思います (個人的には -1 がない方がいろいろと綺麗になるので良いとは思うのですが...).

2. 双対定理

2.1. 茨

定義3 (タッチ).
$G$をグラフとする. 二つの部分集合 $F_1,F_2\subseteq G$ が
・$V(F_1)\cap V(F_2)\neq \emptyset$, もしくは
・ある二つの頂点 $v_1\in V(F_1),\,v_2\in V(F_2)$ が存在して $\{v_1,v_2\}\in E(G)$
であるとき, タッチしているという.

定義4 (茨).
グラフ $G$ の部分グラフの族 $\mathcal{B}=\{B_1,\ldots,B_m\}$ が以下の条件全てを満たすとき, $\mathcal{B}$ を 茨 という:
・各 $B_i$ は 連結グラフである.
・どの $i,j\in\{1,\ldots,m\}$ に対して $B_i$ と $B_j$ はタッチしている.

定義5 (カバー).
グラフ$G$ の部分グラフ族 $\mathcal{B}=\{B_1,\ldots,B_m\}$ を考える. 頂点部分集合 $C$ が $\mathcal{B}$ をカバーしているとは, すべての $i=1,\ldots,m$ に対して $C\cap B_i\neq \emptyset$ を満たすことをいう. この$C$を$\mathcal{B}$のカバー集合とよぶ. $\mathcal{B}$ のオーダーを, $\mathcal{B}$ のカバー集合のうち最小サイズとする.

定義6 (茨数).
グラフ $G$ の茨数 $\mathrm{br}(G)$ を, $G$の茨の中での最大オーダーで定める. すなわち
$$\mathrm{br}(G) = \max_{\mathcal{B}}\min_{C} |C|$$
である ($\mathcal{B}$ は $G$ の茨全体, $C$ は $\mathcal{B}$ のカバー全体を動く).

例 (グリッドグラフ)

$n\times n$ のグリッドグラフ $G$ を考えます. 下図のような頂点部分集合$B_{ij}$を十字集合と呼ぶことにします.

図1. 茨の例

フォーマルな定義は, グリッドグラフ $G$ の頂点集合が $V(G)=\{(i,j):i,j\in [n]\}$ だとすると, $B_{ij} = \{(y,x):y=i \text{ or }x=j\}$ となります. ここで, $\mathcal{B}=\{B_{ij}\}_{i,j}$ は 茨 になっていることがわかると思います. また, 図右のように, 頂点集合 $\{(i,i)\}_{i=1}^n$ はこの $\mathcal{B}$ のカバーになっていることが分かります. つまり, $\mathrm{br}(G)\geq n$ が分かります.

2.1. 双対定理

木幅と茨数に関する以下の双対定理が成り立ちます.

定理8 (強双対性) [Seymour, Thomas, 1993]
任意の連結グラフ $G$ に対し
$$\min_{(T,\mathcal{V})} \max_{t\in V(T)} |V_t| = \max_{\mathcal{B}}\min_{C} |C|$$
すなわち, $\mathrm{br}(G)=\mathrm{tw}(G)+1$.

コメント (NP=coNP ?).
木幅の計算はNP困難であることが知られており, 木幅$\leq k$ かどうかの判定問題は NP完全です. 一方で定理7を見ると木幅$\geq k'$であることの witness として茨を考えれば良いじゃないかという気もしてきます. ということは, 木幅$\leq k$の判定問題は coNP に属す, すなわち NP=coNP の証明になってしまうのではないか？ ということが気になります. 結論からいう茨そのものは指数サイズになりえるため答えはノーです.

定理8の証明はDiestelのグラフ理論の和訳されたものに載っています. 自分はM2の夏に読んだのですが, 少し長くて大変だった記憶があります.

2.2 例 (グリッドグラフ)

先ほど $n\times n$ のグリッドグラフ $G$ を考えていました. オーダー $n$ の茨を構成していたので, $\mathrm{tw}(G)\geq n-1$ が示されたことになります.

実は, $\mathrm{tw}(G)=n$ になります. というのも木分解として

図2. 最適な木分解 (パス分解にもなる)

このように与えることができます (この木分解により, $\mathrm{tw}(G)\leq n$が言える).

一方で, 最適な茨としては

図3. 最適な茨

図1の青を上図のようにちょっと修正したもので与えられます.

3. 結論

オーダーの高い茨が構成できれば, 木幅の下界を示すことができます. これであなたも立派なグラフマイナー研究者ですね!

駆け足で眺める平均計算量の雰囲気

0. 概要

アルゴリズムの研究をしていると「任意の入力に対して正答する高速なアルゴリズムがあるか」を気にしますが、平均計算量では「ランダムに与えられた入力に対して高確率で正答する高速なアルゴリズムがあるか」を気にします。例えばソーシャルネットワークの解析をしようと思ったとき、どんなグラフでも絶対正答する$\Theta(n^{100})$時間アルゴリズムを使っていては計算が終わらないので困ってしまいます。それよりも、ソーシャルネットワークの特性を利用した高速なアルゴリズムを使うべきです。平均計算量では、そのような高速なアルゴリズムがあるかどうかを議論するわけです（もちろん、入力クラスを制限して高速なアルゴリズムを設計するというアプローチもあります）。

この記事では、平均計算量にはどういうテクニックがあるかを、以下の章立てで簡単に紹介します。
1. 導入
2. 分布問題の例
3. フレームワーク
4. 最悪時から平均時への帰着
5. 誤り訂正符号


(＊) 想定読者としてはアルゴリズム・計算量に興味のある学部生レベルを仮定しています（なので、専門家から見ると物足りないものになってしまうと思います）。

1. 導入

計算量理論のブランチの一つに平均計算量 (average-case complexity) という分野があります。読者の多くは「問題XはNP困難である」「問題Yは2近似アルゴリズムがある」「問題ZはFPTに属する」といった論文を読んだり書いたりしたことがあるでしょう。これらの結果は最悪計算量 (worst-case complexity) に関するものです。つまり「任意の入力に対して解くアルゴリズムが存在するかどうか」を焦点にあてています。

一方で平均計算量では、何らかの確率分布にしたがって生成された入力を高確率で解くアルゴリズムを要請します。この研究には0章で述べたものを含め三つの応用があります。

応用1. 実際のインスタンスに対する計算量
応用2. セキュリティ (困難なインスタンスの生成)
応用3. 脱乱択化

応用1については0章でも述べた通りで、容易に想像できると思います。

応用2について述べます。セキュリティの分野で「素因数分解の困難性に基づいた暗号」などについて聞いたことがあると思います。暗号を設計するとき、その復号化は敵対者からすると難しいものでなければなりません。つまり、困難な問題があればそれは暗号理論に応用できる、ということです。ここで「困難」の意味に注意が必要です。実は、最悪計算量の困難性（例えばNP困難性）だとあまり意味がないです。というのも、最悪計算量の困難性は「任意のアルゴリズムに対して意地悪なインスタンスが存在する」ことを主張するからで、そもそもどんなアルゴリズムでも解けないようなインスタンスを設計することは出来ないです。一方平均計算量の困難性は「任意のアルゴリズムに対してうまくいかないような、多項式時間でサンプリングできる入力分布が存在する」といったことを主張するので、困難なインスタンスはただサンプリングするだけで容易に生成することができます。

応用3は話としては少し難しいので分からなくても良いです。実は、平均的に困難な判定問題があったらその問題を使って擬似乱数生成器 (PRG: Pseudo-Random Generator) を構成することができます。このPRGは、$m$ビットの一様ランダム文字列を受け取って $2^{\Omega(m)}$ ビットの「一様ランダムっぽい」文字列を出力するというものです。例えば多項式時間乱択アルゴリズムを考えたとき、そのアルゴリズムで用いられるランダムネスは多項式ビットなので、PRGで生成した $2^{\Omega(m)}=\mathrm{poly}(n)$ ビットのランダム文字列で代用することができます。このとき、$m=O(\log n)$ なので、長さ $m$ のビットを全探索することができます。こうすると多項式時間乱択アルゴリズムを多項式時間決定的アルゴリズムに置き換えることができるので、P=BPPとなるわけです（BPPは多項式時間乱択アルゴリズムで解ける問題のクラス）。

2. 分布問題の例

3.1. 最大マッチング問題

最大マッチング問題（グラフを入力としてうけとり、最大マッチングを出力せよという問題）を考えます。この問題は多項式時間で解くことができます。簡単のため、ここでは辺に重みはないものとします。既存の中で（最悪計算量の意味で）最速なアルゴリズムは $O(|V|\sqrt{|E|})$時間アルゴリズムです [Micali and Vazirani, 1980]。では、ランダムグラフ上ではより高速に解けるのでしょうか。

ランダムグラフとして、Erdős–Rényi ランダムグラフ $G(n,p)$ を考えます。このランダムグラフは $n$ 頂点を持ち、各頂点対が独立に確率 $p$ で接続されたグラフです。$p=p(n)$ は $n$ の関数になることもあり、例えば $p=1/\sqrt{n}$といったものを考えたりします。今回は、疎なグラフを考えたい（密なグラフだと入力長が大きくなるので）ので、$p=O(\log n/n)$ とします。このとき、辺の本数は$\binom{n}{2}p=\Theta(n\log n)$くらいなので、Micali and Vazirani のアルゴリズムを適用すると大体 $n^{1.5}$ 時間になりますね。

実は、[Erdős and Rényi, 1966]は以下の定理を示しています：

定理1.
数列 $(c_n)_{n\in\mathbb{N}}$ に対し、$p=p(n)=(\log n+c_n)/n$ とする. 偶数頂点数のグラフ $G$ が完全マッチングを持つという事象を $\mathcal{M}(G)$ で表す. このとき、以下が成り立つ：
$$\lim_{n\to\infty}\Pr[ \mathcal{M}(G(n,p)) ] = \begin{cases} 0 & \text{if $c_n\to-\infty$},\\ \mathrm{e}^{-\mathrm{e}^{-c}} & \text{if $c_n \to c$},\\ 1 & \text{if $c_n \to \infty$}. \end{cases}$$

ですので、例えば$p>2\log n/n$ なら高確率で最大マッチングのサイズは$n/2$になることが分かります。それでは、最大マッチング自体は簡単に見つかるのでしょうか？この問題はこれまでいろいろと研究されており（意外なことに、かなりの大御所もこのトピックで論文を書いています！）ので、結果だけを簡単にまとめます。

・十分大きい定数 $C$ に対し, $p>C\log n/n$ ならば, $O(n\log n)$ 時間で見つかる [Angluin and Valiant, 1979].

・$p=\Theta(n^{-1})$のとき、$(1-o(1))$-近似線形時間アルゴリズムが存在する [Karp and Sipser, 1981]. このアルゴリズムは、辺集合 $M\leftarrow \emptyset$ から開始し, (I) 次数1の頂点があればその頂点に接続している辺を $M$ に追加, (II) どの頂点も次数2以上になったらランダムに辺を選んで $M$ に追加しその辺の両端点をグラフから削除し、その後 (I) に戻る という二つの操作を可能な限り繰り返すという単純なものです。

・上記のKarp-Sipserのアルゴリズムは, $p=c/n$ かつ $0<c<\mathrm{e}$ ならば実は最大マッチングを出力する [Aronson, Frieze, Pittel, 1998].

・$p>\log n/n$ ならば, 最短交互道をできるだけとってXORをとるよく知られたアルゴリズム (Hopcroft-Karp や Micali-Vazirani) が実は $O(m\log n/\log (np))$ 時間で終わる ($m\approx n^2p/2$ は辺の本数) [Motwani, 1994]. Hopcroft-KarpやMicali-Vaziraniのアルゴリズムでは最短交互道の長さが高々 $\sqrt{n}$ 種類しかないことを示したため最悪計算量が$m\sqrt{n}$になるが, ランダムグラフ上だとエキスパンダー性を持っているので最短交互道の長さが高々 $O(\log n/\log (np))$ になるという性質を利用している.

・上記のMotwaniの結果は、$p>C/n$ ($C$ は 十分大きな定数) でも成り立つ [Bast, Mehlhorn, Schafer, and Tamaki, 2006].

3.2. クリーク問題

最大クリーク問題（グラフを入力として受け取り、最大クリークを出力せよという問題）を考えます。この問題はよく知られるNP困難問題です。ここでは、最大クリークのサイズではなくクリークそのものを出力せよという問題を考えています。この問題はランダムグラフ上で解けるでしょうか？

ランダムグラフとして、Erdős–Rényi ランダムグラフ $G(n,1/2)$ を考えます。このグラフは、$n$ 頂点ラベル付きグラフ全体から一様ランダムにとってきたものと見なすことができるので、理論の人からすると最も自然なランダムグラフになっています。

$G(n,1/2)$ 上では最大クリークのサイズは大体 $2\log n$ になることが知られています。正確には、$\Pr[G(n,1/2)=(2+o(1))\log n]=1-o(1)$ が示せます。これは、この記事で紹介している First-order method と Second-order method を組み合わせることで証明できます。

実は、単純な貪欲法（任意に選んだ一つの頂点から始めて、クリークになるように一つずつ頂点を追加していき、追加できなくなったら出力するアルゴリズム）を用いると高確率でサイズ $(1-o(1))\log n$ のクリークが得られます。つまり貪欲法は 2-近似アルゴリズム となるわけです（最悪計算量の世界では、P$\neq$NPの下では最大クリークは任意の定数$\epsilon>0$に対して $n^{1-\epsilon}$-近似が出来ないことが知られています）。ここで、一つの疑問が生じます。

疑問.
$G(n,1/2)$ を受け取って高確率でサイズ $\geq (1+\epsilon)\log n$ のクリークを出力する多項式時間アルゴリズムは存在するか？ ($\epsilon>0$ は小さい定数)

実はこの問題は、Karpが1976年に提示して以来、未解決です。多くの変種の問題が考えられており、最も有名なものに planted clique と呼ばれる問題があります。

問題 (Planted Clique)
$G\sim G(n,1/2)$ とし、 $V(G)$からランダムに$k$個の頂点を選びそれを $S$ とする. $S$内の全頂点ペアに辺を追加（つまり$S$はサイズ $k$ のクリークになる）して得られるグラフを$H$とする。アルゴリズムはグラフ $H$ を与えられるので、クリークにした頂点集合 $S$ を出力せよ。

$G(n,1/2)$はサイズ $2\log n$ のクリークを持つので、$k\gg 2\log n$ ならば全探索を使えば検出することができます。また、$k=n/2$とかならば入力そのものが半分完全グラフになるので、貪欲法などで簡単に検出できます。実は $k\geq C\sqrt{n\log n}$ ならば、次数の高い順に$k$個の頂点をとってくればそれが正解であるということが証明できます [Kučera, 1995]。 また, $k\geq C\sqrt{n}$ の場合は隣接行列の第二固有ベクトルなどを見ることで多項式時間で解くことができます [Alon, Krivelevich, and Sudakov, 1998]。AKS98の論文はこの業界の中ではとても有名です。

Planted Clique が注目されている理由の一つには、暗号理論への応用が期待できるからです。自分はあまり詳しくはないのですが、サイズ $k$ のクリーク $S$ という秘密にしたい情報を、$G(n,1/2)$ に埋め込むことで隠せるというのが嬉しいのだと思います。

2. フレームワーク

平均計算量の基本的な用語の定義を並べます。

定義2. (分布問題)
分布問題 $(\Pi,\mathcal{D})$ とは, 問題 $\Pi$ と分布列 $\mathcal{D}=(\mathcal{D}_1,\mathcal{D}_2,\ldots)$ の組である。
問題$\Pi$とその入力$x$に対し、$\Pi(x)$でその問題の答えを表す。

コメント.
問題 $\Pi$ は判定問題とは限りません。数え上げ問題や最適化問題も含みます。分布列$\mathcal{D}_n$はサイズ $n$ の入力上の分布です。例えば $G(n,1/2)$などを考えます。また、「大きいクリークを出力せよ」の類の問題の場合、$\Pi(x)$は大きいクリークのなっている頂点部分集合の族だとします。このとき、アルゴリズムは$\Pi(x)$の要素を出力していれば正解したと見なすことにします。

定義3. (分布問題を解くアルゴリズム)
- 決定的アルゴリズム $A$ が以下を満たすとき、$A$は分布問題 $(\Pi,\mathcal{D})$ を成功確率 $\delta$ で解くという：
$$\forall n\in\mathbb{N},\,\,\,\Pr_{x\sim \mathcal{D}_n}\left[A(x)=\Pi(x)\right] \geq \delta.$$
また、このアルゴリズム $A$ のことを特に ヒューリスティクス と呼ぶ。
- 乱択アルゴリズム $B$ が以下を満たすとき、$B$は分布問題 $(\Pi,\mathcal{D})$を成功確率 $\delta$ で解くという：
$$\forall n\in\mathbb{N},\,\,\,\Pr_{x\sim \mathcal{D}_n}\left[\Pr_B\left[B(x)=\Pi(x)\right]\geq 2/3 \right] \geq \delta.$$

コメント.
- ヒューリスティクスという用語は、最悪時計算量のアルゴリズムと区別するときに用いられます。
- 乱択アルゴリズムの定義に出てくる $2/3$ という数字に意味はありません (1/2より真に大きい定数であればなんでも良いです）。というのも、$B$を繰り返して多数決をとるというアルゴリズムを考えればいくらでも大きくできるからです。


平均計算量の世界では、「任意のアルゴリズムをもってしても成功確率が低い」ような問題が難しいとされます。もちろん、成功確率は低ければ低いほど良いです。

4. 最悪時から平均時への帰着

最悪時から平均時への帰着 (worst-case to average-case reduction) について説明します。2章では、ランダムグラフ上ならば最悪計算量よりも高速に解けるというような例をみてきました（planted cliqueのように、平均時でもなお困難であろうと予想されている問題もみました）。この章では、最悪計算量と平均計算量が同等であるような問題の一つとしてパーマネントの計算問題に着目します。

問題 ($\mathrm{Perm}_q$)
$q$を素数とする。入力として $n\times n$ 行列 $A=(a_{ij})\in \mathbb{F}_q$ が与えられるので、$A$のパーマネント
$$\mathrm{perm}(A) := \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i\sigma(i)}$$
を計算せよ。ここで $S_n$ は $\{1,\ldots,n\}$ 上の置換全体の集合である.

$q$が大きいときの $\mathrm{Perm}_q$ は #P困難問題の一つとしてとても有名で、多項式時間では解けないだろうと言われています（$q=2$ならば行列式と同じになるので多項式時間で解けてしまいます）。また、二部グラフの完全マッチングの数え上げ問題を特殊ケースとして含みます。

ここで、$q$を十分大きな素数として、分布問題として $(\mathrm{Perm}_q,\mathcal{D})$ を考えます。ここで $\mathcal{D}=(\mathcal{D}_1,\ldots,)$ において各 $\mathcal{D}_n$ は $\mathbb{F}_q^{n\times n}$ 上の一様ランダムな分布とします（なので各成分が独立に$\mathbb{F}_q$からとってきたときなランダム行列になる）。

定理4.
$q>n^2$を素数とする. $(\mathrm{Perm}_q,\mathcal{D})$ を成功確率 $1-0.1n^{-1}$ で解く 多項式時間ヒューリスティクスが存在するならば、$\mathrm{Perm}$ を解く多項式時間乱択アルゴリズムが存在する。

証明.
$R\in \mathbb{F}_q^{n\times n}$ を$\mathcal{D}_n$からとってきたランダム行列とする。これに対し、多項式 $H:\mathbb{F}_q \to \mathbb{F}_q$ を$H(t)=\mathrm{perm}(A+tR)$ で定める。このとき、$H$は$n$次多項式である。なぜならば、$\mathrm{perm}(A)$ は定義より、各成分 $a_{ij}$ に関する多項式であって全次数が$n$だからである。

$H$ は一変数多項式なので、$H(1),\ldots,H(n+1)$が分かれば多項式補間により各係数が分かり、全ての$t$に対して $H(t)$ が計算できるようになる。そこで、$H(0)=\mathrm{perm}(A)$を計算し出力すれば良い。

つまり、$H(1),\ldots,H(n+1)$を計算すれば良いが、$H(t)=\mathrm{perm}(A+tR)$をみたとき、$R$がランダム行列なので $A+tR$ もランダム行列となっており、その周辺分布は $\mathcal{D}_n$ そのものになっている。したがって $t\neq 0$ ならば $H(t)$は仮定のヒューリスティクスを用いることで計算できる。

このヒューリスティクスの成功確率は $1-0.1n^{-1}$ なので、全ての$i\in\{1,\ldots,n+1\}$に対して成功する確率は、ユニオンバウンドにより$\geq 0.9$となる。

つまり、確率0.9以上で$\mathrm{Perm}$を解く乱択アルゴリズムが得られたが、このアルゴリズムを繰り返して多数決をとることによって確率はいくらでも大きくできる。

（証明終）

コメント.
定理4の証明は [Lipton, 1991] によるものです。ここでの成功確率 $1-0.1/n$ はすごく強いことを要請していますが、これを緩めた研究というのがその後に続いています。[Cai, Pavan, Sivakumar, 1999] はこれを $1/\mathrm{poly}$ にまで下げました。専門用語を使うと、Reed-Muller符号のリスト復号アルゴリズム と Permに対する sumcheck protocol に基づく対話証明を組み合わせることで下げています。

パーマネント以外にも最悪時から平均時への帰着が知られている問題はいくつかあり、最短ベクトル問題 (SVP) や 離散対数問題などでも知られています。これらの問題は、自分自身への帰着にもなっているので、ランダム自己帰着 (random self-reducibility) とも呼ばれており、計算量理論においてとても重要な概念の一つとなっています。

5. 誤り訂正符号

今までは具体的な問題を見てきましたが、ここからは一気に計算量理論っぽくなります。平均計算量の理論では誤り訂正符号が重要なツールとして活躍するので、それについて紹介したいと思います。前章で述べた最悪時から平均時への帰着の話を誤り訂正符号の観点から解釈することが本章の目標です。以後は、特に断らない限り判定問題のみを考えます。以下の約束事をもうけます。

・判定問題は $f:\{0,1\}^*\to\{0,1\}$によって表現される。
・自然数 $n\in\mathbb{N}$に対して $f_n:\{0,1\}^n\to\{0,1\}$を$f$ の $\{0,1\}^n$ への制限とする。また、$f_n$は長さ$2^n$のビット列と同一視する。つまり $f_n\in \{0,1\}^{2^n}$。
・逆に、$M=2^k$の形になっているとき、文字列$h\in \{0,1\}^M$は一つの判定問題 $h:\{0,1\}^k\to\{0,1\}$ とも見なす。
・分布族 $\mathcal{D}=(\mathcal{D}_1,\ldots)$ は一様分布のみを考える。つまり各 $\mathcal{D}_n$は$\{0,1\}^n$上の一様分布とする。

アルゴリズム $A$ に対し、$\mathrm{str}_n(A)\in \{0,1\}^{2^n}$ を、全ての$x\in\{0,1\}^n$ に対して $A(x)$ を計算して横に並べてできる文字列 $(A(x))_{x\in\{0,1\}^n}$としましょう。

これから次の定理を直感的に証明したいと思います。

定理5（informal).
最悪計算量の意味で難しい問題 $f$ から 平均計算量の意味で難しい問題 $g$ を構成できる。

二つの文字列 $a,b\in\{0,1\}^m$ に対し、それらのハミング距離 $d(a,b)$ を
$$d(a,b) := \Pr_{i\in \{1,\ldots,m\}} [a[i]\neq b[i] ]$$
と定めます（よく使われるハミング距離の定義と定数倍しか変わらないので本質的に等価です）。

もし $A$ が $f_n$ を計算するアルゴリズムであるならば、$\mathrm{str}_n(A)$ は 文字列 $f_n\in\{0,1\}^{2^n}$ と一致するはずです。また、$B$ が関数 $g_m$ を成功確率 $\delta$ で計算するヒューリスティクスであるならば、
$$\Pr_{x\in\{0,1\}^m}[B(x)=g_n(x)] \geq \delta$$
より、$\mathrm{str}_n(B)$ と $g_m$ のハミング距離は $1-\delta$ 以下となります。

ここで、誤り訂正符号とは何なのかを説明します（定義はArora & Barak の本に基づきます）。

定義6 (誤り訂正符号）
$\gamma \in [0,1]$に対し、関数 $E:\{0,1\}^n \to \{0,1\}^m$ が以下の条件を満たすとき、$E$を距離$\gamma$ の誤り訂正符号 と呼ぶ：
$$\forall x,y\in \{0,1\}^n,\,\, x\neq y \Rightarrow d(E(x),E(y)) \geq \gamma.$$

誤り訂正符号のイメージ。赤い点が$\{0,1\}^n$を表していて、$E$の像はまばら。

誤り訂正符号はもともと、通信のための技術として研究されていました。送信者がメッセージ $x\in\{0,1\}^n$ を受信者に送ろうとしたとき、そのまま送ってしまうと通信路でノイズが入ってしまい、別の文字列 $\hat{x}\in\{0,1\}^n$ を受信してしまうことがあります。このノイズは、$x$の各ビットが独立に確率$\epsilon$で反転してしまうものだとしましょう。すると$d(x,\hat{x}) \approx \epsilon$ になりますよね。そこで、距離 $2\epsilon$の誤り訂正符号 $E$を使って $y=E(x)$ を受信者に送ります。するとこのメッセージにもノイズがかかるので受信者は $\hat{y}$ を受信します。今、$d(y,\hat{y})\leq \epsilon$ です。一方でどんなメッセージ $x'\neq x$ に対して、$y'=E(x')$ は、誤り訂正符号の性質より $d(y,y')\geq 2\epsilon$ となるので、$d(y',\hat{y})\geq \epsilon$ が成り立ちます。

$y$と$y'$は遠いが, $y$と$\hat{y}$は近いので、$\hat{y}$から$x$を復元できるかも？

ですので（細かい等号とかは無視するとして）、受信した $\hat{y}$ から $x$を復元できる可能性があります。このように、$\hat{y}$から$x$を復元することを復号化と呼びます。

計算量の話に戻ります。解きたい問題を$f$とします。各$n$に対して、$f_n$を計算するのが目標です。

重要なコメント.
「各$n$に対して$f_n$が計算できる」ことと「$f$が解ける」ことは本来は意味が全く異なります。前者は「全ての$n$に対してあるアルゴリズム$A_n$ が存在して $A_n$ は $f_n$ を計算する」という意味ですが、後者は「あるアルゴリズムが存在して全ての$n$に対して$A$は$f_n$を計算する」という意味なので量化子の順番が違いますよね。この違いは計算量理論においてはとても重要で、前者の「解ける」を「nonuniformに解ける」、後者の「解ける」を「uniformに解ける」と言います。uniformの意味で多項式時間アルゴリズムで解ける判定問題の全体をクラスPと呼びますが、nonuniformの意味で多項式時間アルゴリズムで解ける判定問題の全体はクラス P/poly と呼びます。包含関係としては P $\subseteq$ P/poly が明らかに成り立ちますが、一方で P/poly の属するが P に属さない問題が存在するのでこの包含関係は真です。ひとまずこの記事では nonuniform の意味で解けるかどうかを議論します。

$E:\{0,1\}^{2^n} \to \{0,1\}^M$ を距離 $\gamma$ の誤り訂正符号とします ($E$の定義域のビット長に注意してください）。また、$M=2^k$の形で書けるとします。今、$f_n\in\{0,1\}^{2^n}$ は文字列だったので、$E(f_n) \in \{0,1\}^M$ を考えましょう。この文字列は一つの判定問題と見なすことができますね。この問題を $h_k:\{0,1\}^k\to\{0,1\}$ と書くことにしましょう。

$h_k=E(f_n)$ を成功確率 $\geq 1-\gamma/2$ で計算するヒューリスティクス $A$ があると仮定します。このとき、$\mathrm{str}_A(h_k) \in \{0,1\}^M$ は $E(f_n)$ とのハミング距離が $\leq \gamma/2$ となります。すなわち、我々は $E(f_n)$ から距離が近い文字列へのランダムアクセスを手に入れたことになります。ここまでの議論は、誤り訂正符号の説明・画像においては、$y\leftarrow E(f_n)=h_k$、$y'\leftarrow \mathrm{str}_A(h_k)$ と見なしていますね。

ここで、$\mathrm{str}_A(h_k)$を復号してみると、計算したい文字列 $f_n$ が復元できます！これはつまり $f_n$ が計算できるというわけです。

コメント.
実際のアルゴリズムでは $\mathrm{str}_A(h_k) \in \{0,1\}^M$ をメモリに格納したりはしません。$\mathrm{str}_A(h_k)$ へのランダムアクセスを使って $f_n$ へのランダムアクセスを構成しようとしています。このように、符号化したあとの文字列へのランダムアクセスを使って復元したいメッセージへのランダムアクセスを構成することを局所復号 (local decoding) と呼びます。

ここまでの議論では、$h_k$ を平均的に解くアルゴリズムが存在するならば $f_n$ を任意の入力で計算するアルゴリズムが構成できるということを見てきました。ですので、$f_n$が最悪計算量の意味で困難な問題であったならば、$h_k$は平均計算量の意味で困難な問題であることが帰結として得られます。これが最悪時から平均時への帰着というものです。