確率的計算量 | 計算理論

1 確率的 Turing 機械

定義 1.1. 確率的 Turing 機械 (probabilistic Turing machine) $M$ は、通常の決定性多テープ TM に読取り専用の乱数テープを加えた機械である。乱数テープのヘッドは位置 $0$ から始まり、乱数ビットを一つ読むたびに右へ一マス進み、左へ戻らない。乱数テープの各マスには、互いに独立で

\Pr[r_i=0]=\Pr[r_i=1]=\frac12

を満たすビットが置かれる。入力 $x$ と乱数列 $r$ を固定すれば計算は決定的になるので、その計算を $M(x;r)$ と書く。

$M$ が全ての長さ $n$ の入力と全ての乱数列に対して $p(n)$ 段以内に停止するなら、読み取る乱数は高々 $p(n)$ ビットである。未使用のビットも補って $r\in\{0,1\}^{p(n)}$ とすると、受理確率 (acceptance probability) は

\Pr_r[M(x;r)\text{ が受理する}] =\frac{|\{r\in\{0,1\}^{p(|x|)}:M(x;r)\text{ が受理する}\}|} {2^{p(|x|)}}

である。

無限乱数列そのものへ未定義の確率を割り当てず、まず有限 prefix にだけ確率を定める。最初の $m$ ビットだけで決まる事象 $A$ に対して、

\Pr[A] =\frac{|\{u\in\{0,1\}^m:u\text{ が }A\text{ を満たす}\}|}{2^m}

と定める。より長い prefix へ未使用ビットを補っても、分子と分母が同じ $2$ の冪倍になるので値は変わらない。停止時間に関する無限和と極限は、次の補題によって有限 prefix の確率から定める。

補題 1.2. 一方向乱数テープを読む確率的 TM の、非負整数値または $\infty$ をとる停止時間を $T$ とする。次が成り立つ。

打切り時間 $m$ までの事象 $\{T>m\}$ は最初の $m$ 個以下の乱数ビットだけで決まる。 $\Pr[T=\infty]=\lim_{m\to\infty}\Pr[T>m], \qquad \mathbb E[T]=\sum_{j\ge0}\Pr[T>j]$ と定めることができる。特に $\mathbb E[T]<\infty$ ならば $\Pr[T=\infty]=0$ である。
各 $m\in\mathbb N$ に対して $Y^{(m)}=\min\{Y,m\}$ が有限個の乱数ビットだけで決まる、非負整数値または $\infty$ 値の確率変数 $Y$ を考える。 $\mathbb E[Y]=\lim_{m\to\infty}\mathbb E[Y^{(m)}]$ と定めると、全ての実数 $a>0$ について $\Pr[Y\ge a]\le\frac{\mathbb E[Y]}a$ である。
事象 $A_1,\ldots,A_k$ が互いに素な有限乱数ビット区間だけでそれぞれ決まるならば、 $\Pr[A_1\cap\cdots\cap A_k] =\prod_{i=1}^k\Pr[A_i].$ 同じ区間から定まる有限値確率変数 $Y_i$ について、 $\mathbb E\left[\prod_{i=1}^kY_i\right] =\prod_{i=1}^k\mathbb E[Y_i]$ である。

証明. $T^{(m)}=\min\{T,m\}$ とする。 $T^{(m)}$ は高々 $m$ 段の計算だけで決まり、一段で乱数を高々一つ読むので、最初の $m$ ビットだけに依存する。有限和の順序を交換すると、

\begin{aligned} \mathbb E[T^{(m)}] &=\sum_{t=0}^m t\,\Pr[T^{(m)}=t]\\ &=\sum_{t=0}^m\sum_{j=0}^{t-1}\Pr[T^{(m)}=t] =\sum_{j=0}^{m-1}\Pr[T>j]. \end{aligned}

右辺は $m$ とともに非減少なので、その極限を $\mathbb E[T]$ と定める。事象 $\{T>m\}$ は $m$ とともに減少し、全ての $m$ で生き残る乱数列が $T=\infty$ を与えるため、 $\Pr[T=\infty]$ を表示された極限で定める。 $\mathbb E[T]<\infty$ なら級数の各項 $\Pr[T>m]$ は $0$ へ収束するので、 $\Pr[T=\infty]=0$ である。

$Y^{(m)}$ は $\{0,\ldots,m\}$ の有限集合に値をとり、仮定により有限 prefix 上の確率変数である。 $m\ge a$ とすると $\{Y^{(m)}\ge a\}=\{Y\ge a\}$ であるから、有限和の各項のうち $Y^{(m)}\ge a$ を満たすものだけを残して

\mathbb E[Y^{(m)}] \ge\sum_{y\ge a}y\Pr[Y^{(m)}=y] \ge a\Pr[Y^{(m)}\ge a] =a\Pr[Y\ge a]

を得る。左辺について $m\to\infty$ の極限を取れば、主張 (2)を得る。特に $\mathbb E[Y]<\infty$ である場合にも、 $Y=\infty$ となる乱数列を除外せずに同じ評価を適用することができる。

主張 (3)を示す。 $A_i$ が依存する区間の長さを $m_i$ とし、その区間で $A_i$ を満たすビット列の個数を $a_i$ とする。区間が互いに素であるため、全区間の割当てで全ての $A_i$ を満たすものは $\prod_i a_i$ 個あり、全割当ては $2^{\sum_i m_i}$ 個ある。したがって、

\Pr[A_1\cap\cdots\cap A_k] =\frac{\prod_i a_i}{2^{\sum_i m_i}} =\prod_i\frac{a_i}{2^{m_i}}.

$Y_i$ の有限値集合を $V_i$ とする。直前に証明した事象の積公式を各 $\{Y_i=y_i\}$ へ適用し、有限和を分配すると、

\begin{aligned} \mathbb E\left[\prod_iY_i\right] &=\sum_{(y_1,\ldots,y_k)\in V_1\times\cdots\times V_k} \left(\prod_i y_i\right) \Pr[Y_1=y_1,\ldots,Y_k=y_k]\\ &=\sum_{(y_1,\ldots,y_k)} \prod_i\bigl(y_i\Pr[Y_i=y_i]\bigr)\\ &=\prod_i\sum_{y_i\in V_i}y_i\Pr[Y_i=y_i] =\prod_i\mathbb E[Y_i]. \end{aligned}

全ての和は有限なので、和の順序交換に追加の収束仮定は不要である。▨

乱数を固定すると決定的計算になるため、独立反復では各回に互いに素な乱数ビット区間を割り当てる。補題 1.2により、各回の受理事象または誤り事象の共通部分の確率は各確率の積になる。

2 片側誤り、零誤り、両側誤り

定義 2.1. 言語 $L\subseteq\Sigma^*$ が $\mathsf{RP}$ (RP) に属するとは、ある確率的 TM $M$ と多項式 $p$ が存在し、 $M$ が全ての入力と全ての乱数列で $p(|x|)$ 段以内に停止し、任意の $x\in\Sigma^*$ について

\begin{cases} x\in L\ \Longrightarrow\ \Pr_r[M(x;r)\text{ が受理する}]\ge\frac12,\\ x\notin L\ \Longrightarrow\ \Pr_r[M(x;r)\text{ が受理する}]=0 \end{cases}

を満たすことをいう。

$\mathsf{RP}$ の機械は、言語の外側の入力を誤って受理しないが、言語の要素を誤って拒否することがある。

定義 2.2. 言語 $L\subseteq\Sigma^*$ が $\mathsf{coRP}$ (coRP) に属するとは、ある確率的 TM $M$ と多項式 $p$ が存在し、 $M$ が全ての入力と全ての乱数列で $p(|x|)$ 段以内に停止し、任意の $x\in\Sigma^*$ について

\begin{cases} x\in L\ \Longrightarrow\ \Pr_r[M(x;r)\text{ が受理する}]=1,\\ x\notin L\ \Longrightarrow\ \Pr_r[M(x;r)\text{ が受理する}]\le\frac12 \end{cases}

を満たすことをいう。

$\mathsf{coRP}$ の機械は、言語の要素を誤って拒否しないが、言語の外側の入力を誤って受理することがある。二つの片側誤りクラスは、補言語を取る操作で互いに移り合う。

命題 2.3. 言語 $L\subseteq\Sigma^*$ について、 $L\in\mathsf{coRP}$ であることと $\overline L=\Sigma^*\setminus L\in\mathsf{RP}$ であることは同値である。

証明. $L\in\mathsf{coRP}$ とし、定義の機械 $M$ と多項式 $p$ を取る。 $M$ の受理と拒否を入れ替えた機械 $M'$ も、全ての入力と全ての乱数列で $p(|x|)$ 段以内に停止する。 $x\in\overline L$ 、すなわち $x\notin L$ ならば、 $M$ の受理確率は高々 $1/2$ であるから、 $M'$ の受理確率は少なくとも $1/2$ である。 $x\notin\overline L$ 、すなわち $x\in L$ ならば、 $M$ の受理確率は $1$ であるから、 $M'$ の受理確率は $0$ である。したがって $M'$ は $\overline L$ に対する $\mathsf{RP}$ の条件を満たす。

逆に $\overline L\in\mathsf{RP}$ とし、その機械の受理と拒否を入れ替える。 $x\in L$ ならば元の機械の受理確率は $0$ なので、入れ替えた機械は確率 $1$ で受理する。 $x\notin L$ ならば元の機械の受理確率は少なくとも $1/2$ なので、入れ替えた機械の受理確率は高々 $1/2$ である。したがって、入れ替えた機械は $L$ に対する $\mathsf{coRP}$ の条件を満たす。▨

定義 2.4. 言語 $L\subseteq\Sigma^*$ が $\mathsf{ZPP}$ (ZPP) に属するとは、ある確率的 TM $Z$ と多項式 $p$ が存在し、任意の入力 $x$ について次の二条件を満たすことをいう。

$Z(x)$ は確率 $1$ で停止し、停止した全ての計算で $x\in L$ の場合に受理し、 $x\notin L$ の場合に拒否する。
乱数に関する停止時間を $T_Z(x)$ とすると、 $\mathbb E[T_Z(x)]\le p(|x|)$ である。

この条件を満たす機械を零誤り期待多項式時間機械 (zero-error expected polynomial-time machine) という。

定義 2.5. 言語 $L\subseteq\Sigma^*$ が $\mathsf{BPP}$ (BPP) に属するとは、ある確率的 TM $M$ と多項式 $p$ が存在し、 $M$ が全ての入力と全ての乱数列で $p(|x|)$ 段以内に停止し、任意の $x\in\Sigma^*$ について

\begin{cases} x\in L\ \Longrightarrow\ \Pr_r[M(x;r)\text{ が受理する}]\ge\frac23,\\ x\notin L\ \Longrightarrow\ \Pr_r[M(x;r)\text{ が受理する}]\le\frac13 \end{cases}

を満たすことをいう。

$\mathsf{BPP}$ の機械は、言語の内側と外側の両方で誤る可能性があるが、どの入力でも正しい結論を返す確率が少なくとも $2/3$ である。

例 2.6. 成分が $0$ と $1$ の $n\times n$ 整数行列の三つ組を標準的な方法で符号化した語を $\langle A,B,C\rangle$ と書き、言語を

L=\{\langle A,B,C\rangle:AB\ne C\}

と定める。次の機械 $M$ を考える。 $M$ は、入力が正しい符号でなければ直ちに拒否する。正しい符号ならば乱数ビットを $n$ 個読んでベクトル $r\in\{0,1\}^n$ を作り、行列とベクトルの積 $Br$ 、 $A(Br)$ 、 $Cr$ を整数の演算で順に計算し、 $A(Br)\ne Cr$ の場合に受理する。行列とベクトルの積一回は成分の乗算と加算 $O(n^2)$ 回で計算することができるため、 $M$ は全ての入力と全ての乱数列で入力長の多項式段数以内に停止する。

$AB=C$ ならば、結合法則により任意の $r$ について $A(Br)=(AB)r=Cr$ であるから、受理確率は $0$ である。 $AB\ne C$ ならば、 $D:=AB-C$ は零行列でないので、 $d_{ij}\ne0$ となる成分を取ることができる。 $r_j$ 以外の成分を任意に固定すると

(Dr)_i=d_{ij}r_j+\sum_{k\ne j}d_{ik}r_k

であり、 $r_j=0$ と $r_j=1$ に対する二つの値の差は $d_{ij}\ne0$ である。したがって、固定した成分ごとに $(Dr)_i=0$ となる $r_j$ の値は高々一つであり、 $Dr=0$ となる $r\in\{0,1\}^n$ は高々 $2^{n-1}$ 個である。ゆえに

\Pr_r[M(\langle A,B,C\rangle;r)\text{ が受理する}] =\Pr_r[Dr\ne0]\ge\frac12

であり、 $M$ は定義 2.1の二条件を満たす。よって $L\in\mathsf{RP}$ である。

同じ検査で受理の向きだけを入れ替え、正しい符号に対して $A(Br)=Cr$ の場合に受理する機械を $M'$ とすると、 $AB=C$ の入力は確率 $1$ で受理され、 $AB\ne C$ の入力の受理確率は高々 $1/2$ であり、正しい符号でない入力は受理されない。したがって $M'$ は言語 $\{\langle A,B,C\rangle:AB=C\}$ に対する定義 2.2の二条件を満たす。一回の検査も成功確率の数値 $1/2$ も共通であり、どちら側の入力で誤り確率が $0$ になるかがクラスを区別する。

$n=2$ の場合を一つ計算する。

A=\begin{pmatrix}1&1\\0&1\end{pmatrix},\qquad B=C=\begin{pmatrix}1&0\\0&1\end{pmatrix}

では $AB=A\ne C$ であり、 $D=AB-C=\begin{pmatrix}0&1\\0&0\end{pmatrix}$ 、 $Dr=(r_2,0)^{\mathsf T}$ である。四つの乱数ベクトルのうち $r_2=1$ となる二つだけが $Dr\ne0$ を与えるため、 $M$ の受理確率はちょうど $1/2$ である。

3 零誤りと二種類の片側誤り

零誤り期待多項式時間から最悪時多項式時間の片側誤りを得る方向では、期待時間の二倍で計算を打ち切る。逆方向では、二つの片側誤り機械のうち、正しい結論を保証する側が成功するまで反復する。

定理 3.1.

\mathsf{ZPP}=\mathsf{RP}\cap\mathsf{coRP}

である。

証明. 最初に $L\in\mathsf{ZPP}$ とし、 $Z$ と期待時間上界 $p$ を定義の機械と多項式とする。 $p(n)\ge1$ となるように、必要なら $p$ を $p+1$ へ置き換える。入力 $x$ で $Z$ を $2p(|x|)$ 段だけ実行し、その時点で停止していなければ拒否する機械 $R$ を構成する。補題 1.2 (2)により

\Pr[T_Z(x)>2p(|x|)] \le\frac{\mathbb E[T_Z(x)]}{2p(|x|)} \le\frac12

である。 $x\in L$ ならば $Z$ が時間内に停止した場合に $R$ は受理するので、受理確率は少なくとも $1/2$ である。 $x\notin L$ ならば $Z$ は受理することがなく、 $R$ の受理確率も $0$ である。したがって $R$ は $\mathsf{RP}$ の機械である。

同じ打切りで、時間切れの場合に受理する機械 $C$ を構成する。 $x\in L$ ならば、 $Z$ が時間内に停止すれば正しく受理し、時間切れでも $C$ は受理するので、受理確率は $1$ である。 $x\notin L$ ならば、 $C$ が受理するのは時間切れの場合だけであり、その確率は高々 $1/2$ である。したがって $C$ は $\mathsf{coRP}$ の機械である。これで $\mathsf{ZPP}\subseteq\mathsf{RP}\cap\mathsf{coRP}$ を得る。

逆に、 $L\in\mathsf{RP}\cap\mathsf{coRP}$ とする。 $R$ を $L$ に対する $\mathsf{RP}$ の機械、 $C$ を $L$ に対する $\mathsf{coRP}$ の機械とする。次の一回の試行を、毎回新しい独立な乱数で反復する。

$R(x)$ と $C(x)$ を実行する。
$R(x)$ が受理したら受理して停止する。
$C(x)$ が拒否したら拒否して停止する。
どちらの保証付き結論も得られなければ次の試行へ進む。

$x\in L$ ならば $C$ は拒否せず、 $R$ が受理した場合だけ全体が受理する。この結論は正しい。一回の停止確率は $R$ の受理確率であり、少なくとも $1/2$ である。 $x\notin L$ ならば $R$ は受理せず、 $C$ が拒否した場合だけ全体が拒否する。この結論も正しく、一回の停止確率は少なくとも $1/2$ である。各試行には互いに素な乱数ビット区間を割り当てるので、補題 1.2 (3)により、どちらの場合も試行回数 $N$ について

\Pr[N>j]\le2^{-j}

であり、

\Pr[N=\infty] =\lim_{j\to\infty}\Pr[N>j] \le\lim_{j\to\infty}2^{-j}=0

となる。また、同補題の停止時間の定義により

\mathbb E[N] =\sum_{j\ge0}\Pr[N>j] \le\sum_{j\ge0}2^{-j}=2

となる。一回の試行時間を共通の多項式 $q(|x|)$ で抑えると、総時間は $q(|x|)N$ 以下であり、その期待値は $2q(|x|)$ 以下である。結論は停止した全ての計算で正しいので、構成した機械は零誤り期待多項式時間機械である。これで逆包含を得る。▨

4 独立反復による誤り減少

片側誤りでは、誤り得ない結論を一度でも得たか、全ての試行で得たかによって出力を決める。両側誤りでは、独立試行の多数決を用いる。

定理 4.1. $L\in\mathsf{RP}$ とし、定義の一回の受理確率下界を $1/2$ とする。独立に $k$ 回実行し、少なくとも一回受理したら受理する機械では、 $x\notin L$ の受理確率は $0$ のままであり、 $x\in L$ の拒否確率は高々 $2^{-k}$ である。

$L\in\mathsf{coRP}$ の場合、独立に $k$ 回実行して全ての回が受理した場合だけ受理すれば、 $x\in L$ の受理確率は $1$ のままであり、 $x\notin L$ の受理確率は高々 $2^{-k}$ である。

証明. $\mathsf{RP}$ の場合、 $x\notin L$ では各回の受理確率が $0$ なので、少なくとも一回受理する確率も $0$ である。 $x\in L$ では各回の拒否確率が高々 $1/2$ である。独立性により、全 $k$ 回が拒否する確率は各確率の積であり、高々 $(1/2)^k$ である。

$\mathsf{coRP}$ の場合、 $x\in L$ では各回が確率 $1$ で受理するので、全ての回も確率 $1$ で受理する。 $x\notin L$ では各回の受理確率が高々 $1/2$ であり、独立性により全 $k$ 回が受理する確率は高々 $(1/2)^k$ である。▨

両側誤りの多数決について、Chernoff 境界の一般形を仮定せず、指数モーメントを直接評価する。

補題 4.2. $X_1,\ldots,X_k$ を独立な $\{0,1\}$ 値確率変数とし、 $\Pr[X_i=1]\le1/3$ とする。このとき

\Pr\left[\sum_{i=1}^kX_i\ge\frac k2\right] \le \left(\frac4{3\sqrt2}\right)^k.

特に $\rho=4/(3\sqrt2)<1$ と置けば、右辺は $\rho^k$ で指数的に減少する。

証明. $S=\sum_iX_i$ と置く。事象 $S\ge k/2$ では $2^S\ge2^{k/2}$ なので、補題 1.2 (2)を非負変数 $2^S$ へ適用すると、

\Pr[S\ge k/2] \le\frac{\mathbb E[2^S]}{2^{k/2}}

となる。各 $X_i$ は互いに素な有限乱数ビット区間から定まり、その値は $0$ または $1$ である。したがって、有限和を直接分配すると、

\begin{aligned} \mathbb E[2^S] &=\sum_{(x_1,\ldots,x_k)\in\{0,1\}^k} 2^{x_1+\cdots+x_k} \Pr[X_1=x_1,\ldots,X_k=x_k]\\ &=\sum_{(x_1,\ldots,x_k)} \prod_{i=1}^k\bigl(2^{x_i}\Pr[X_i=x_i]\bigr)\\ &=\prod_{i=1}^k \sum_{x_i\in\{0,1\}}2^{x_i}\Pr[X_i=x_i] =\prod_{i=1}^k\mathbb E[2^{X_i}]. \end{aligned}

第2の等号では補題 1.2の事象の積公式を用いた。 $p_i=\Pr[X_i=1]\le1/3$ とすると

\mathbb E[2^{X_i}] =(1-p_i)2^0+p_i2^1 =1+p_i\le\frac43.

したがって

\Pr[S\ge k/2] \le\frac{(4/3)^k}{2^{k/2}} =\left(\frac4{3\sqrt2}\right)^k.

また $16<18$ なので $4/(3\sqrt2)<1$ である。▨

定理 4.3. $L\in\mathsf{BPP}$ とする。定義の機械を独立に奇数回 $k$ 実行し、多数決を返す機械の誤り確率は、全ての入力で

\left(\frac4{3\sqrt2}\right)^k

以下である。したがって、任意の $0<\varepsilon<1$ に対し

k\ge \frac{\log(1/\varepsilon)} {\log(3\sqrt2/4)}

を満たす奇数 $k$ を選べば、誤り確率を $\varepsilon$ 以下にすることができる。

証明. 入力 $x$ を固定し、第 $i$ 回の試行が誤った結論を返す事象の特性変数を $X_i$ とする。 $x\in L$ と $x\notin L$ のどちらの場合も、 $\mathsf{BPP}$ の定義から $\Pr[X_i=1]\le1/3$ である。各回に互いに素な乱数ビット列を用いるため $X_1,\ldots,X_k$ は独立である。多数決が誤るなら、奇数 $k$ 回のうち少なくとも $(k+1)/2>k/2$ 回が誤る。したがって、補題 4.2により誤り確率は $\rho^k$ 以下である。 $\rho^k\le\varepsilon$ を $k$ について解けば表示された条件を得る。各試行が多項式時間であり、固定した $k$ 、または入力長の多項式以下の $k$ を選ぶ場合には総時間も多項式である。▨

系 4.4.

\mathsf{ZPP}\subseteq\mathsf{RP}\subseteq\mathsf{BPP}, \qquad \mathsf{ZPP}\subseteq\mathsf{coRP}\subseteq\mathsf{BPP}.

証明. 最初の二つの $\mathsf{ZPP}$ の包含は定理 3.1から従う。 $\mathsf{RP}$ の機械を二回独立に実行して OR を取ると、言語の要素の受理確率は少なくとも $1-(1/2)^2=3/4$ 、外側の受理確率は $0$ である。したがって、 $\mathsf{BPP}$ の $2/3,1/3$ 条件を満たす。 $\mathsf{coRP}$ の機械を二回独立に実行して AND を取ると、言語の要素の受理確率は $1$ 、外側の受理確率は高々 $(1/2)^2=1/4$ である。したがって、こちらも $\mathsf{BPP}$ に属する。▨

注意 4.5 (アルゴリズムと計算量クラス). 一つの乱択アルゴリズムには、対象とする問題、入力表現、実行時間、および入力ごとの成功確率がある。これに対して $\mathsf{RP}$ 、 $\mathsf{coRP}$ 、 $\mathsf{ZPP}$ 、 $\mathsf{BPP}$ は言語のクラスであり、全入力に対する量化と一つの多項式上界を満たす機械の存在によって定まる。特定の入力で高い成功率を観測したことだけでは、そのアルゴリズムがいずれかの計算量クラスの定義を満たすという結論を得ることができない。

5 演習

問題 5.1.

$\mathsf{RP}\subseteq\mathsf{NP}$ と $\mathsf{coRP}\subseteq\mathsf{coNP}$ を示せ。
$M$ を $L$ に対する $\mathsf{BPP}$ の機械とし、奇数 $k$ を固定する。入力 $x$ と乱数列 $r$ に対して $M(x;r)$ を $k$ 回実行し、その結論の多数決を出力する機械 $M_k$ を考える。ここで $k$ 回の実行はすべて同じ乱数列 $r$ を用いる。すべての $x$ について、 $M_k$ が誤る確率は $M$ が誤る確率に等しいことを示せ。
一回の誤り確率が $1/2$ 以下の $\mathsf{RP}$ 機械について、誤り確率を $2^{-20}$ 以下にする反復回数と出力規則を答えよ。
$Z$ を $L$ に対する零誤り期待多項式時間機械とし、期待時間の上界を $p\geq1$ とする。正の整数 $k$ について、 $Z$ を $2^kp(|x|)$ 段で打ち切り時間切れで拒否する機械 $R_1$ と、 $Z$ を $2p(|x|)$ 段で打ち切り時間切れで拒否する試行を互いに素な乱数で $k$ 回行い、一回でも受理すれば受理する機械 $R_2$ を考える。どちらも $x\notin L$ を受理せず、 $x\in L$ を拒否する確率が $2^{-k}$ 以下であることを示し、二つの機械の最大実行段数を比較せよ。

解答 (演習の要点).

$L\in\mathsf{RP}$ とし、定義の機械 $M$ と多項式 $p$ を取る。検証器 $V$ は入力 $(x,r)$ について $r\in\{0,1\}^{p(|x|)}$ であることを確かめ、乱数テープの内容を $r$ として $M(x;r)$ を決定的に模倣し、その結論を出力する。模倣は $p(|x|)$ 段以内で終わるので、 $V$ は多項式時間で停止する。 $x\in L$ ならば受理確率は $1/2$ 以上であり正であるから、 $M(x;r)$ が受理する $r\in\{0,1\}^{p(|x|)}$ が存在し、 $V(x,r)$ が受理する。 $x\notin L$ ならば受理確率は $0$ であり、受理確率の定義の分子が $0$ であるから、 $M(x;r)$ が受理する $r$ は存在しない。よって $V$ は $L$ の多項式時間検証器であり、§E18.11 定理 3.1により $L\in\mathsf{NP}$ である。

$L\in\mathsf{coRP}$ ならば、命題 2.3により $\overline L\in\mathsf{RP}\subseteq\mathsf{NP}$ であり、§E18.11 定義 5.1により $L\in\mathsf{coNP}$ である。
同じ乱数列 $r$ を用いると、入力 $x$ と $r$ を固定した計算 $M(x;r)$ は決定的であるから、 $k$ 回の実行はすべて同じ結論を返す。 $k$ 個の同じ結論の多数決はその結論自身であるから、すべての $r$ について $M_k(x;r)$ と $M(x;r)$ の結論は一致する。受理確率は結論が受理である $r$ の割合であるから、 $M_k$ と $M$ の受理確率は等しく、誤る確率も等しい。定理 4.3の証明では各回に互いに素な乱数ビット区間を割り当て、補題 1.2 (3)により各回の誤り事象の独立性を用いるが、この $M_k$ では $k$ 回の誤り事象が一致し、誤り確率は減らない。
独立に $20$ 回実行し、一回でも受理したら受理する。言語の要素に対する全回拒否の確率は高々 $2^{-20}$ である。
$Z$ は停止した全ての計算で正しく答えるので、 $x\notin L$ のとき $Z$ は受理せず、時間切れでは拒否するから、 $R_1$ も $R_2$ も $x\notin L$ を受理しない。

$x\in L$ とする。 $R_1$ が拒否するのは時間切れの場合だけであるから、補題 1.2 (2)により拒否確率は $\Pr[T_Z(x)\geq2^kp(|x|)]\leq\mathbb E[T_Z(x)]/(2^kp(|x|))\leq2^{-k}$ である。 $R_2$ の各試行が時間切れになる確率は、同じ不等式により $1/2$ 以下である。 $R_2$ が拒否するのは $k$ 回の試行がすべて時間切れになる場合だけであり、各試行は互いに素な乱数ビット区間を用いるので、補題 1.2 (3)によりその確率は $(1/2)^k=2^{-k}$ 以下である。

最大実行段数は、 $R_1$ が $2^kp(|x|)$ 段に打切りの管理の定数倍を加えたもの、 $R_2$ が $2kp(|x|)$ 段に同じ管理を加えたものである。同じ誤り上界 $2^{-k}$ に対して、 $R_2$ の段数は $k$ について線形、 $R_1$ の段数は $k$ について指数的に増える。とくに $k$ が入力長の多項式で増える場合、 $R_2$ は多項式時間のままであるが、 $R_1$ はそうではない。

▨

§E18.14確率的計算量

1 確率的 Turing 機械

2 片側誤り、零誤り、両側誤り

3 零誤りと二種類の片側誤り

4 独立反復による誤り減少

5 演習

参考文献

前提記事