解答例（問A.Xおよび問1.X）

「計算量理論演習問題」の解答メモです。自分の勉強用につくったものなので、内容に保証はありません。

問A.3(1)

$\exists C>0;\,\exists N>0;\,l\geq N\, \Rightarrow \,f(l,\,\delta) \leq 2^{-Cl\delta^2}$

問A.3(2)

$E[(1+\delta)^X]=\sum_{n=0}^l(1+\delta)^n{}_lC_np^n(1-p)^{l-n}=\sum_{n=0}^l{}_lC_n\left\{(1+\delta)p\right\}^n(1-p)^{l-n}$
$\,\,\,\,\,\,\,\,=\left\{(1+\delta)p+(1-p)\right\}^l=(1+p\delta)^l$

問A.3(3)

$f(l,\,\delta)\cdot(1+\delta)^{pl(1+\delta)}$ は、 $x<\lfloor pl(1+\delta) \rfloor$ で 0、 $x\geq \lceil pl(1+\delta) \rceil$ で $(1+\delta)^{pl(1+\delta)}$ となる階段状の関数の期待値である。

一方、右辺は $(1+\delta)^x$ という関数の期待値であるが、この関数は先の階段上の関数より常に大きい。

従って、 $f(l,\,\delta)\cdot(1+\delta)^{pl(1+\delta)} \leq E[(1+\delta)^X]$

問A.3(4)

問A.3(3)の結果より、

$f(l,\,\delta)\leq\frac{(1+p\delta)^l}{(1+\delta)^{pl(1+\delta)}}$

次の級数展開を右辺の分子・分母に適用する。

$\ln(1+\delta)=\delta-\frac{\delta^2}{2}+{\rm O}(\delta^3)$

（分子）= $\exp\left\{\left(p\delta-\frac{p^2\delta^2}{2}+{\rm O}(\delta^3)\right)l\right\}$

（分母）= $\exp\left\{\left(\delta-\frac{\delta^2}{2}+{\rm O}(\delta^3)\right)pl(1+\delta)\right\}$

従って、

$f(l,\,\delta)\leq\exp\left\{-\frac{p(1+p)}{2}l\delta^2+l{\rm O}(\delta^3)\right\}=2^{-Cl\left(\delta^2+{\rm O}(\delta^3)\right)}$

$\left(C:=\frac{p(1+p)}{2}\log e\right)$

問1.1(1)

$(n-1)+(n-2)+\dots+1=\frac{n(n-1)}{2}$

（参考）Selection sort

問1.1(2)(a)

最良ケースでn回、最悪ケースで(2n-1）回

問1.1(2)(b)

2n個の要素をn個づつのグループA、グループBに分けると、問1.1(2)(a)の結果を考慮して、

T(2n) =（グループAを整列するための最大比較回数）
　　　　+（グループBを整列するための最大比較回数）
　　　　+ (2n-1)
　　　= 2T(n) + (2n-1)
　　　= 2T(n) + O(n)

問1.1(2)(c)

先の結果より、

$T(n)=2T\left(\frac{n}{2}\right)+(n-1)=2\left\{2T\left(\frac{n}{2^2}\right)+(\frac{n}{2}-1)\right\}+(n-1)$

$\,\,\,\,\,\,\,\,=2^2T\left(\frac{n}{2^2}\right)+(n-2)+(n-1)=\,\cdots\,=2^kT\left(\frac{n}{2^k}\right)+\sum_{i=1}^k(n-i)$

$\,\,\,\,\,\,\,\,=2^kT\left(\frac{n}{2^k}\right)+nk-\frac{k(k+1)}{2}\,\,\,\,(k=1,2,\cdots)$

ここで、 $n=2^k \left(\Leftrightarrow k=\log n\right)$ の場合を考えると、第2項が支配的となり、 $T(n)=O(n\log n)$ であることが分かる。

問1.2

深さkの二分木の葉は、高々 $2^{k-1}$ 枚。

n個の整数の大小関係は、 $n!$ 通り。

従って、 $2^{k-1} > n!$ より、 $k>\frac{\log n!}{\log 2} + 1$

スターリングの公式より、 $n! \simeq \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\,\,\,(n \gg 1)$ に注意して、 $k = \Omega(n\log n)$ が得られる。

問1.3

$M_1,\,M_6,\,M_7$ の計算量は、 $I_0\,:=2\times\left(\frac{n}{2}\right)^2+T\left(\frac{n}{2}\right)$
※ $\frac{n}{2}\times \frac{n}{2}$ 行列の和が2回とそれらの積が1回

$M_2,\,M_3,\,M_4,\,M_5$ の計算量は、 $I_1\,:=\left(\frac{n}{2}\right)^2+T\left(\frac{n}{2}\right)$
※ $\frac{n}{2}\times \frac{n}{2}$ 行列の和が1回とそれらの積が1回

従って、 $T(n)=8\left(\frac{n}{2}\right)^2+3I_0+4I_1$
※ $\frac{n}{2}\times \frac{n}{2}$ 行列の和が8回と $M_1,\,\cdots,\,M_7$ の計算

以上より、

$T(n) = 7T\left(\frac{n}{2}\right) + Cn^2\,\,\,\,\left(C\,:=\frac{9}{2}\right)$

$\,\,\,\,\,\,\,\,=7\left\{7T\left(\frac{n}{2^2}\right)+C\left(\frac{n}{2}\right)^2\right\}+Cn^2=7^2T\left(\frac{n}{2^2}\right)+\left(\frac{7}{2^2}+1\right)Cn^2$

$\,\,\,\,\,\,\,\,=7^2\left\{7T\left(\frac{n}{2^3}\right)+C\left(\frac{n}{2^2}\right)^2\right\}+\left(\frac{7}{2^2}+1\right)Cn^2=7^3T\left(\frac{n}{2^3}\right)+\left\{\left(\frac{7}{2^2}\right)^2+\left(\frac{7}{2^2}\right)+1\right\}Cn^2$

$\,\,\,\,\,\,\,\,\cdots\,=7^kT\left(\frac{n}{2^k}\right)+\sum_{i=0}^{k-1}\left(\frac{7}{2^2}\right)^iCn^2\,\,\,\,\left(k=1,\,2,\,\cdots\right)$

$\,\,\,\,\,\,\,\,=7^k T\left(\frac{n}{2^k}\right) + \left\{\left(\frac{7}{2^2}\right)^k-1\right\} C' n^2\,\,\,\,\left(C'\,:=\frac{C}{\frac{7}{2^2}-1}\right)$

ここで、 $k=\log n$ の場合を考えて、 $m^{log n} = n^{log m}$ の関係に注意すると、

$T(n) = n^{\log 7} + C'n^2\left(n^{\log\frac{7}{2^2}}-1\right) = n^{\log 7} + C'n^2\left(n^{\log 7-2}-1\right)$

$\,\,\,\,\,\,\,\,=n^{\log 7} + C'n^{\log 7} - C'n^2$

最後に $\log 7 > 2$ に注意すると、 $T(n) = O(\log 7)$ が得られる。

（参考）Strassen algorithm

問1.4

利用終了時刻の早いもの順に並べる。

（理由）
申し込み全体の中で、利用終了時刻が最も早い申し込みをAとする。Aを選択しなかったことで、代わりに選択できる可能性のある申し込みは、すべて、Aの終了時刻と利用時間が重なっている。つまり、Aの代わりに選択できるのは、1つだけである（Aを選択しないことで、2つ以上の申し込みが選択できるようになることはない）。

この時、Aの代わりにどの1つを選んだとしても、その終了時刻はAより遅いので、他の申し込みに与える影響はAより大きい。つまり、最初の利用者としてAを選択するのが最適である。

つぎに、Aと利用時間が重ならないすべての申し込みについて、上記と同じ議論を繰り返すことで、その中で利用終了時刻が最も早いものが次に選べることになる。以下、この議論を繰り返せばよい。

（参考）Independent sets in interval intersection graphs

問1.5(1)

$g(u)=f(v_1)+f(v_2)+\cdots+f(v_k)$ 　（自明）

$f(u)=\max\left\{g(u),\,\,1+g(v_1)+g(v_2)+\cdots+g(v_k)\right\}$ 　　（独立集合にuを含む場合と含まない場合で場合分けして、大きい方を取る）

問1.5(2)

木の高さについて、下から順番に $f(u)$ を帰納的に計算していく。ある高さ以下の $f(u)$ がすべて分かれば、(1)の結果を使って、1つ上の高さの $f(u)$ が決まる。

（参考）木分解とグラフ・アルゴリズム (最適化と数え上げ) (PDF)

問1.6

n=2の時は、下図のxor回路（大きさ3）が作れる。

入力を1つ追加するごとに、「前段のxor回路の出力」と「新しい入力」の2つ新たなxor回路に入力すればよい。入力を1つ追加するごとに、大きさが3増えるので、一般に 3n-3 の大きさになる。

問1.7

入力数nの数学的帰納法で示す。n=1の場合は、2個の素子ではパリティ計算回路はつくれないことは、しらみつぶしで分かる。

n=kの時、パリティ計算回路は少なくとも(3k-3)個の素子を持つと仮定して、n=k+1の場合を考える。

まず、任意の1つの入力xについて、それが接続する素子は、2個以上あることを示す。

仮に1個のAND素子（Aと呼ぶ）のみに接続するとした場合、Aに対するもう一方の入力はxとは独立に決まり、x以外の入力を調整して0にできたとする。この時、xの入力は0, 1どちらであっても回路の出力は変わらず、パリティ計算回路の動作として矛盾する。もう一方の入力が0になるような状態がない（もう一方の入力は常に1である）とすれば、Aの出力は常にxからの入力に一致するので、素子Aを削除して、Aの出力先にxからの入力を直接に接続しても回路として等価である。つまり、この場合、矛盾するか、もしくは、Aを削除した等価回路が得られる。

同じく、1個のOR素子（Aと呼ぶ）のみに接続するとした場合、もう一方の入力が0の場合と1の場合を入れ替えて同じ議論をすれば、矛盾するか、もしくは、この素子を削除してAの出力先にxからの入力を接続した等価回路が得られる。

上記で等価回路が得られた場合は、等価回路について同じ議論を繰り返せば、どこかで同じ矛盾が生じる（もしくは、回路の最終出力が、xからの入力に一致して、矛盾する）。

これで、入力xは少なくとも2個の素子に接続することが分かった。この先は、2個の素子の組み合わせ、および、xと素子の間のNOTの有無で場合分けして考える。

(1) xと両方の素子の間にどちらもNOTが無い場合。

(1-1) AND素子（Aと呼ぶ）とAND素子（Bと呼ぶ）に接続する場合

xからの入力を0に固定すると、この回路は、k入力のパリティ計算回路として動作する。この時、AとBの出力は常に0になるので、これらを削除して、それぞれの出力先（A'、B'と呼ぶ。A'とB'は一致する場合もある）にxの入力を接続しても回路として等価である。さらにA'、B'のどちらかがAND素子の場合、その出力も常に0になるので、同様にその素子を削除できる。あるいは、A'、B'のどちらかがOR素子の場合、その出力はもう一方からの入力に一致するので、その素子を削除して、その出力先にもう一方からの入力を接続しても回路として等価である。

つまり、xからの入力を0に固定した場合、もとの回路から少なくとも3つの素子を削除しても等価な回路となる。これは、k入力のパリティ計算回路なので、帰納法の前提より、少なくとも(3k-3)個の素子を持つ。逆にいうと、今考えている回路は、少なくとも、(3k-3)+3 = 3(k+1)+3 個の素子を持つ。

(1-2) AND素子（Aと呼ぶ）とOR素子（Bと呼ぶ）に接続する場合

xからの入力を0に固定すると、Aについては、(1-1)と同様の議論で削除できて、Aの出力先には、xからの入力（つまり0）が接続される。Bについては、その出力はもう一方からの入力に一致するので、Bを削除して、その出力先にもう一方からの入力を接続できる。さらに、Aの元々の出力先がAND素子の場合、その出力は常に0になるので、やはり削除できる。OR素子の場合、その出力はもう一方からの入力に一致するので、やはり削除できる。以上より、少なくとも3個の素子が削除できるので、(1-1)と同じ結論が得られる。

(1-3) OR素子（Aと呼ぶ）とOR素子（Bと呼ぶ）に接続する場合

xからの入力を1に固定すると、A、Bの出力は常に1になるので、(1-1)と同様の議論で、少なくとも3個の素子が削除できて、(1-1)と同じ結論が得られる。

(2) xと素子の間（一方の素子、もしくは、両方の素子の間）にNOTがある場合。

このパターンのあらゆる組み合わせにおいて、xが接続する素子の一方（Aとする）について、その出力が定数になるようにxからの入力が固定できる。(1)と同様の議論を繰り返して、素子Aとその先の素子が削除できる。もう一方の素子についても同様に削除できる。

つまり、この場合も少なくとも3個の素子が削除できるので、(1)と同じ結論が得られる。