読者です 読者をやめる 読者になる 読者になる

めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

解答例(問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} 未満にできることを示す。

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

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

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

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

{\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 AlgorithmsPolynomial 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

と変形する。次に、[tex:2

問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 として与えるようにすれば、必ず正解を与える助言付き機械が構成できる。

(参考)P/poly

問3.10

{\rm NP}\subseteq{\rm PP} を示す。NPに属する判定問題 A を解く機械を M とすると、A(x)M(x) の関係は次のようにまとめられる。

A(X) M(x)
1 1 or 0
0 0

この時、新しい機械 M' を次のように定義する。

  • M(x)=1 の時は、1 を回答する。
  • M(x)=0 の時は、確率 \frac{1}{2} で 1 を回答する。

上記の表と併せて見ると、機械 M' は PP の条件を満たすことが分かる。

続いて、{\rm PP}\subseteq{\rm PSPACE} を示す。

PPに属する判定問題 A を解く機械を M(x,\,r) とする。ここで、r は、入力 x の大きさの多項式長 f(|x|) で抑えられる長さの乱数である。ここで、新しい機械 M' を次のように定義する。

  • 多項式長 f(|x|) で抑えられる長さのすべての r について、M(x,\,r) を計算してその結果を多項式長の作業用テープに記録する。その結果から多数決で回答を決める。(ぴったり同数の場合は 0 を回答する。)

この機械 M' は、PPの定義から必ず正解を与えるので、PSPACE の条件を満たす。

(参考)PP (complexity)