解答例（問3.X） - めもめも

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

問3.1

${\rm C} \subseteq {\rm coC}$ より、任意の $X$ について、 $X \in {\rm C} \,\Rightarrow\,X \in {\rm coC}$ ---- (1)

この時、

$A \in {\rm coC}\,\Rightarrow\,\overline{A} \in {\rm C}$ （C, coC の定義）

$\,\,\,\,\,\,\,\,\Rightarrow\,\overline{A} \in {\rm coC}$ （(1)より）

$\,\,\,\,\,\,\,\,\Rightarrow\,A \in {\rm C}$ （C, coC の定義）

従って、 ${\rm coC} \subseteq {\rm C}$ 。つまり、 ${\rm C}={\rm coC}$

問3.2

$A(x)=1$ として、 $M(x)=1$ となる確率を $p$ とする。この時、 $M(x)$ が 1 になるまで繰り返し計算した場合、 $n$ 回目までに 1 になる確率は、

$P=\sum_{i=0}^{n-1}(1-p)^ip = \frac{1-(1-p)^n}{1-(1-p)}p = 1-(1-p)^n$

従って、任意の $\delta > 0$ に対して、 $(1-p)^n < \delta$ となる $n$ をとれば、 $P > 1-\delta$ とできる。

つまり、 $M(x)$ の計算を最大 $n$ 回繰り返す機械を $M'(x)$ を用いれば、任意の確率で判定することが可能。（ $\delta$ に対して $n$ は一意の定数として決まるので、M' の計算時間は M の計算時間の定数倍であり、多項式時間で抑えられる。）

問3.3(1)

${\rm ZPP'} \subseteq {\rm ZPP}$ を示す。 $A\in{\rm ZPP'}$ として、対応する機械を $M(x)$ とする。この時、新たな機械 $M'(x)$ を次のように定義する。

$M(x)$ の計算結果が ? の場合は、? 以外の結果が得られるまで $M(x)$ の計算を繰り返す。

この時、 $M(x)$ が ? を返す確率を $r<\frac{1}{2}$ とすると、n回目の繰り返しで停止する確率は $r^{n-1}(1-r)$ で与えられる。 $M(x)$ の一回の計算時間は、 $p(|x|)$ 以下であるので、 $M'(x)$ の計算時間の期待値 $E_t$ は、次の不等式で抑えられる。

$E_t \leq \sum_{n=1}^{\infty}r^{n-1}(1-r)\times np(|x|) = \frac{p(|x|)}{1-r} < 2p(|x|)$

従って、 $E_t$ は多項式 $2p(|x|)$ で抑えられる。つまり、 $A \in {\rm ZPP}$

続いて、 ${\rm ZPP} \subseteq {\rm ZPP'}$ を示す。 $A\in{\rm ZPP}$ として、対応する機械を $M(x)$ とする。この時、新たな機械 $M'(x)$ を次のように定義する。

$M(x)$ がある多項式時間 $p(|x|)$ 以内に終了しなかった場合は、そこで停止して ? を返す。

この時、 $p(|x|)$ を適切に定義すると、 $M'(x)$ が ? を返す確率を $\frac{1}{2}$ 未満にできることを示す。

一般に、マルコフの不等式より、計算時間 $T$ が $t$ よりも長くなる確率は、次の不等式で抑えられる。

${\rm Pr}[T \geq t] \leq \frac{E[T]}{t}$

ここに、 $E[T]$ は計算時間の期待値で、仮定より、 $E[T] \leq q(|x|)$ ----- (1)

したがって、計算時間 $T$ が $t$ 以下に抑えられる確率は、

${\rm Pr}[T \leq t] \geq 1-\frac{E[T]}{t}$

であり、 $t\geq 2E[T]$ であれば、 ${\rm Pr}[T \leq t] \geq \frac{1}{2}$ となる。つまり、 $p(|x|)=2q(|x|) \geq 2E[T]$ （∵(1)）とおけば、計算時間が $p(|x|)$ を超えて ? を出力する確率は、 $\frac{1}{2}$ 未満になる。

問3.3(2)

${\rm RP}\cap{\rm coRP} \subseteq {\rm ZPP'}$ を示す。 $A\in{\rm RP}\cap{\rm coRP}$ とすると、RP に対応する機械 M と coRP に対応する機械 M' があって、それぞれ多項式時間限定で次のような結果を出力する。

A(x)	M(x)	M'(x)
1	1(確率1/2以上) or 0	1
0	0	1 or 0(確率1/2以上)

ここで、新たな機械 M'' を次のように定義する。

$M(x)=M'(x)=1$ の時は 1 を出力する。
$M(x)=M'(x)=0$ の時は 0 を出力する。
それ以外の時は ? を出力する。

この時、M'' が ? を出力する確率は $\frac{1}{2}$ 未満であり、 $A\in{\rm ZPP'}$ となる。

続いて ${\rm ZPP'}\subseteq{\rm RP}\cap{\rm coRP}$ を示す。 $A\in{\rm ZPP'}$ とすると、ZPP に対応する機械 M が存在する。ここで、RP に対応する新たな機械 M' を次のように定義する。

$M(x)=1$ の時は 1 を出力する。
$M(x)=0$ の時は 0 を出力する。
$M(x)=?$ の時は 0 を出力する。

これは、 $A(x)=0$ であれば、必ず $M(x)=0$ となる。一方、 $A(x)=1$ の場合は、 $M(x)=0$ となることも起こり得るが、その確率は $\frac{1}{2}$ 未満であり、確かに $A\in{\rm RP}$ となる。

同様に coRP に対応する機械 M'' は次のように定義できる。

$M(x)=1$ の時は 1 を出力する。
$M(x)=0$ の時は 0 を出力する。
$M(x)=?$ の時は 1 を出力する。

（参考）ZPP (complexity)

問3.4(1)

$(x_1+x_2)^n$ の展開は、 $2^n$ の計算量となるので、多項式時間では展開できない。

問3.4(2), 問3.5

うーん。「算術式」と「算術回路」で問題を分ける意図が読み取れませんでした。Schwartz-Zippel Lemmaで一般的に解いてしまう以外の解法を求めているのだとは思いますが・・・。

Schwartz-Zippel Lemmaで一般的に解くならこんな感じ。

補題1: $p(x_1,\,\cdots,\,x_n)$ を体 ${\mathcal F}$ の上で定義された最高次数 $d$ の多項式で、恒等的に 0 ではないとする。この時、有限部分集合 $S \subseteq {\mathcal F}$ から ${y_1,\,\cdots,\,y_n}$ をランダムに取り出したとすると、これが多項式の根を与える（つまり、 $p(y_1,\,\cdots,\,y_n)=0$ となる）確率は、次式で抑えられる。

${\rm Pr}[p(y_1,\,\cdots,\,y_n) = 0] \leq \frac{d}{|S|}$

証明は、CPSC 536N: Randomized Algorithms の Polynomial Identity Testing by the Schwartz-Zippel Lemma [PDF] を参照。

したがって、次の判定機械 M を用いると、coRP 判定が可能になる。

与えられた多項式に対して、 $\frac{d}{|S|} < \frac{1}{2}$ となる十分大きな部分集合 $S$ を取って、ここからランダムに取り出した $y_1,\,\cdots,\,y_n$ を用いて $p(y_1,\,\cdots,\,y_n)$ を計算する。これが 0 にならなかった場合は「恒等的に 0 ではない」、0 になった場合は「恒等的に 0 である」と回答する。

これは、「恒等的に 0 ではない」を誤ることはなく、「恒等的に 0 である」を誤る確率は $\frac{1}{2}$ 未満に抑えられる。

※ 体 ${\mathcal F}$ が有限集合で十分大きな $S$ を取れない場合は、少なくとも $\frac{d}{|{\mathcal F}|}<1$ であればランダムに取り出してテストする操作を繰り返すことで、誤る確率を $\frac{1}{2}$ 未満にすることができる。

問3.6

A(x)=1の場合は、Hの頂点からGの頂点への単射fが存在して、Hの各辺について、その両端点をfで写した点を端点とするGの辺が存在する。この単射fは、多項式長で表現できるので、これが「証拠r」として利用できる。

問3.7(1)

与えられた正の整数をそれ以下の（ランダムに選択した）任意の正の整数で割ってみて、割り切れた場合は、「素数ではない」と判定する。つまり実際に素数ではない場合に、「素数ではない」と判定する確率は0より大きい。逆に素数である場合は、必ず素数であると判定する。

なお、割り切れるかどうかの判定は、選択した整数を繰り返し引いていき、ちょうど0になるか調べれば、多項式時間で判定できる。

問3.7(2)

n-1の「擬似素因数分解」を次の多項式時間限定のアルゴリズムで作成する。まず、素因数 2 をくくりだして、

$n-1 = 2^{k_1} \times n_1$

と変形する。次に、 $2 < x_2 \leq n_1$ なる整数 $x_2$ をランダムに選んで、この整数を因数としてくくり出す。

$n-1 = 2^{k_1} \times x_2^{k_2} \times n_2$

$k_2=0$ の場合は、ここで操作を終了する。そうでない場合は、 $2 < x_3 \leq n_1$ なる整数 $x_3$ をランダムに選んで、この整数を因数としてくくり出す。

$n-1 = 2^{k_1} \times x_2^{k_2} \times x_3^{k_3} \times n_3$

$k_3=0$ の場合は、ここで操作を終了する。そうでない場合は、再度、同じ操作を繰り返していく。この操作を繰り返すごとに、 $n_i$ は $\frac{1}{2}$ 以下になる（つまり、ビット数は必ず減少する）ので、この操作は、 $O(|n-1|)$ （ $n-1$ のビット数以下の繰り返し）で終了する。

最終的に、次のような「擬似素因数分解」が与えられたものとする。

$n-1 = 2^{k_1} \times \prod_{i=2}^{K} x_i^{k_i}$

この時、次の事実が成立する確率は 0 よりは大きい。

(1) 擬似素因数分解が真の素因数分解である

さらに、n が素数であれば、整数 a をランダムに選択して、次の事実が成立する確率も 0 より大きい。

(2) $a^{n-1} \equiv 1\,({\rm mod}n)$ 、かつ、 $p \in (2,\,x_2,\,\cdots,\,x_K)$ のすべての $p$ について $a^{\frac{n-1}{p}} \not\equiv1\,({\rm mod}n)$

したがって、前述のアルゴリズムで与えた $(2,\,x_2,\,\cdots,\,x_K)$ と整数 a について、(1)(2)が実際に成立していることが多項式時間限定で確認できれば、n が素数であることを多項式時間限定において 0 よりも大きい確率で正しく判定することができる。

一般に、指数計算は多項式時間で実施できる（参考：Exponentiation by squaring）ことに注意すると、(2)は多項式時間限定で判定可能である。（ $p \in (2,\,x_2,\,\cdots,\,x_K)$ の個数は $O(|n-1|)$ であることにも注意。）

(1)については、 $(x_2,\,\cdots,\,x_K)$ がすべて素数であることが確認できればよい。ただし、ここでは、これを厳密に確認することはあきらめて、0 よりも大きい確率で正しく判定することにする。（「n が素数であることを 0 よりも大きい確率で正しく判定する」という目標においては、これで十分である。）

これは、当初の n が素数であることを確認する問題と同じことなので、 $(x_2,\,\cdots,\,x_K)$ について、再帰的に同じアルゴリズムを適用していけばよい。この時、再帰的に得られるすべての $x$ の総数は、n-1 のビット数で抑えられるので、擬似素因数分解全体は多項式時間 $O(|n-1|^2)$ で抑えられる。（1回の「擬似素因数分解」が $O(|n-1|)$ の処理で、これを高々 $|n-1|$ 回繰り返す。）

例として、 $n=229$ に対する1回目の擬似素因数分解が次のように与えられたとする。（真の素因数分解ではない。）

$229-1=2^2\times 57$

この場合、2回目以降の擬似素因数分解は、次のように一意に決まる。

$57-1=2^3\times 7$

$7-1=2\times 3$

$3-1=2$

（参考）Primality certificate

問3.8

Mが誤った答を出力する確率を $p\in(0,\,\frac{1}{2})$ とする時、機械 M' を次のように定義する。

$M(x)$ の計算を $l$ 回繰り返して、半数を越えて $M(x)=1$ となった場合は、1 を出力する。そうでなければ、0 を出力する。

この時、M' が誤った答を出力するのは、 $l$ 回の独立試行において、確率 $p$ の事象 X が $\frac{l}{2}$ 回以上発生する場合なので、その確率は $P = {\rm Pr}[X \geq \frac{1}{2}l]$ となる。

ここで、[tex:pl0] を1つ固定すると、問A.3の結果を用いて、次の関係が成立する。

$P \leq {\rm Pr}[X \geq pl(1+\delta)] = 2^{-{\rm \Omega}(l\{\delta^2+{\rm O}(\delta^3)\})}$

従って、試行回数 $l$ を十分に大きくすると、M' が誤った答を出力する確率 $p'$ は、 $p'\in(0,\,\frac{1}{2})$ の範囲で任意に小さくできる。

問3.9(1)

判定問題 D「機械Mに『機械Mを表す文字列』を入力した時に受理しない」はPに属さない。（この判定問題を実装する機械 ${\rm M_D}$ が存在すると仮定すると、 ${\rm D(M_D)}$ は正しく計算できないので矛盾する。）この問題は、次のように、P/polyで実装可能である。

『機械Mを表す文字列』を0の羅列表現 $\{0\}^*$ で表すことにして、 $z_k := {\rm D}(0^k),\,\,{\rm M}(x,\,z_{|x|}):=z_{|x|}$ と定義すればよい。

問3.9(2)

BPPに属する機械 ${\rm M}(x,\,r)$ を考える。 $r$ は入力長の多項式 $f(|x|)$ で抑えられる長さの乱数である。ここで、 $l$ をある定数として、機械 ${\rm M'}(x,\,r')$ を次のように定義する。 $r'$ は $l \times f(|x|)$ で抑えられる長さの乱数である。

$r'$ を $l$ 分割した乱数を $(r_1,\,\cdots,\,r_l)$ として、 ${\rm M}(x,\,r_i)\,\,\,(i=1,\,\cdots,\,l)$ の過半数が 1 を出力した場合は、1 を出力する。さもなくば 0 を出力する。

この時、問3.8と同様の議論により、M' が特定の入力 $x$ に対して誤った答を出す確率は次式で抑えられる。

$P(x) = 2^{-{\rm \Omega}(l\delta^2)}$

つまり、 $l$ を十分大きくとれば、「誤らない確率」は 0 より大きくなる。言い換えると、ある乱数 $r'$ を用いれば必ず正解が得られることを意味している。

ここで、長さ $n$ の入力 $x$ 全体 $(x_1,\,\cdots,\,x_N)$ （これは高々 $2^n$ 個である）を考えて、同じ乱数 $r'$ を用いてこれらすべてを計算することを考える。この時、どれか1つでも誤った答を出す確率 P は次式で抑えられる。

$P \leq \sum_{i=0}^NP(x_i) = N \times 2^{-{\rm \Omega}(l\delta^2)} < 2^{n-{\rm \Omega}(l\delta^2)}$

従って、（ $n$ の多項式の範囲で） $l$ を十分大きく取れば、上記の確率は 1 より小さくなる。言い換えると、長さ $n$ の入力 $x$ すべてに正解を与える乱数 $r'$ が少なくとも1つは存在する。（かつ、その長さは多項式長で抑えられる。）この乱数を機械 M' に助言 $z_n$ として与えるようにすれば、必ず正解を与える助言付き機械が構成できる。