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

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

問2.1

$A \in P$ とする時、定義より、多項式 $\tau$ と $\tau$ 時間限定の機械 M が存在する。十分大きな $k \in N$ について $\tau = O(n^k)$ となるので、この $k$ を用いて、 $A \in {\rm DTime}(n^k)$

従って、 $P \subset \cup_{k\in N}{\rm DTime}(n^k)$

一方、任意の $k \in N$ について、 $P \supset {\rm DTime}(n^k)$ は自明。

従って、 $P \supset \cup_{k\in N}{\rm DTime}(n^k)$

以上より、 $P = \cup_{k\in N}{\rm DTime}(n^k)$

問2.2

$BIT_f \in P$ であり、 $\forall x;\,|f(x)| \leq p(|x|)$ をみたす多項式 $p$ が存在すると仮定する。

この時、次の組に対して、順次、判定問題 $BIT_f$ の結果を順次調べることで、 $f(x)$ を構成できることが分かる。

$(x,\,0,\,0),\,(x,\,0,\,1),\,(x,\,1,\,0),\,(x,\,1,\,1),\,\cdots$

この時、 $|f(x)| \leq p(|x|)$ より、この組の列の長さは、多項式 $2p(|x|)$ で抑えられる。各 $BIT_f$ の計算が多項式時間でできることから、 $f(x)$ は多項式時間で求められる。つまり、 $f \in {\rm FP}$

逆に、 $f \in {\rm FP}$ と仮定する。

この時、 $f(x)$ が多項式時間で求まることから、 $|f(x)|$ は $|x|$ の多項式で抑えられる。（機械は、一度の遷移で高々１文字しか出力できないから。）

したがって、 $f(x)$ の各ビットを0ビット目から順に走査することで、多項式時間以内に、判定問題 $BIT_f$ の答えが得られる。

つまり、 $BIT_f \in P$ であり、 $\forall x;\,|f(x)| \leq p(|x|)$ をみたす多項式 $p$ が存在する。

問2.3

$f,\,g\in {\rm FP}$ として、これらの計算時間を抑える多項式を $p_f,\,p_g$ とする。

$x\,\,\longrightarrow^g\,\,g(x)\,\,\longrightarrow^f f(g(x))$

という2段階の写像を考えると、最初の写像の計算時間は $p_g(|x|)$ で抑えられて、次の写像の計算時間は $p_f(|g(x)|)$ で抑えられる。 $g\in {\rm FP}$ より、 $|g(x)|$ はある多項式 $q(x)$ で抑えられることを考慮すると、 $f\circ g$ の計算時間は、多項式 $p_g + p_f\circ q$ で抑えられる。

問2.4

言えない。反例は次の通り。

$\Sigma = \{0\},\,\,f : 0^k\, \longrightarrow\, 0^{2k}$ とするとき、 $|f(0^k)| = 2k = 2|0^k|$ より $f \in {\rm FP}$

一方、 $f^{\rm iter}(0,\,0^n) = 0^{2^n}$ より、この関数は多項式時間では計算できない。（ $|f^{\rm iter}(0,\,0^n)|=2^n$ が $|(0,\,0^n)|=n$ の多項式で抑えられないため。）

問2.5(1)

$a\,\longrightarrow\,b\,\longrightarrow\,c$ という部分グラフが $G$ に含まれるとする。これは、 $\varphi$ に $(\neg a \vee b)$ と $(\neg b \vee c)$ という節が含まれることと同値で、この時、 $\varphi$ に $(\neg a \vee c)$ という節を加えても論理式として等価であることが分かる。（ $(a,\,b)$ の真偽値のあらゆる組み合わせを考えると証明できる。）これは、 $G$ に $a$ から $c$ への枝を加えることに等しい。

したがって、 $a$ から $\neg a$ に至る経路がある場合、上記の操作を繰り返すことで、 $a\,\longrightarrow\,\neg a$ という枝が追加できて、これは、 $\varphi$ に $(\neg a \vee \neg a)$ という節を加えることに等しい。

ここで、 $a$ と $\neg a$ の両方を通る閉路があるとする。この場合、 $a$ から $\neg a$ に至る経路から $(\neg a \vee \neg a)$ という節が加えられて、一方、 $\neg a$ から $a$ に至る経路から $(a \vee a)$ という節が加えられる。これら両方の節を同時に満たすことはできないので、 $\varphi$ は充足不能となる。これで、必要性が示された。

続いて、十分性を示すために、その準備としてグラフ $G$ の性質を述べておく。

$(x \vee y)$ と $(\neg x\,\rightarrow\,y)$ と $(\neg y\,\rightarrow\,x)$ の3つの論理式は等価であるので、グラフ $G$ を $(x\,\rightarrow\,y)$ という形式の論理式の連言とみなして、これを充足する真偽値の組が発見できれば、元の $\varphi$ が充足できたことになる。

また、 $(\neg x\,\rightarrow\,y)$ と $(\neg y\,\rightarrow\,x)$ は互いの対偶となっていることから、 $G$ の任意の連結部分集合 $A$ について、その対偶に対応する連結集合 $B$ も $G$ に含まれることになる。ただし、 $A$ と $B$ が一致する場合もある。このことから、 $G$ の構造について次の補題が成立する。

[補題1]
$x$ から $y$ および $\neg y$ の両方に接続する経路がある場合、この経路はさらに $\neg x$ にも接続する。

（証明） $x$ から $y$ および $\neg y$ の両方に接続する経路について、その対偶となる経路を考える。

以上の準備を踏まえて、 $x$ と $\neg x$ の両方を通る閉路が存在しないという仮定の下に、 $G$ を充足する真偽値の組を与える具体的なアルゴリズムを示して、十分性の証明とする。

$G$ の任意の頂点 $x$ に着目すると、次のいずれかが必ず成立する。

　(i) $x$ から $\neg x$ に至る経路が存在しない。

　(ii) $x$ から $\neg x$ に至る経路が存在する。

まず、(i)の場合を考える。

この時、任意の変数 $y$ について、 $x$ から接続する経路において、 $y$ と $\neg y$ の両方が含まれることはない。（仮に両方が含まれるとすると、[補題1] より、(i)の前提に矛盾する。）したがって、 $x$ から始まる経路に含まれるすべてのリテラルに真偽値「真」を矛盾なく割り当てられることができる。

また、今、「真」を与えたリテラルの否定について、「偽」を割り当てることも矛盾なく行える。なぜなら、「真」を割り当てたリテラルからなる連結集合を $X$ として、 $G$ にはこの対偶となる連結集合 $X'$ が存在する。 $X'$ は連結集合であり、ここに含まれるリテラルには矛盾なく「偽」を割り当てられる。（ $X'$ の上流には、先ほど「真」を与えたリテラルは存在し得ないことに注意。）

次に、(ii)の場合は、仮定より、 $\neg x$ から $x$ に至る経路が存在しないことになるので、着目する頂点を $\neg x$ に取り替えて、(i)と同じ操作を行う。

続いて、以上の操作でまだ真偽値を割り当てていない頂点がある場合、その中の1つに着目して、先と同じ操作を繰り返すことを考える。

この時、新たに「真」を割り当てるリテラル（ $x$ とする）の接続先に、すでに「偽」を割り当てたリテラル（ $y$ とする）は存在しない。仮に存在したとすると、その対偶となる経路において、 $\neg y$ にはすでに「真」が割り当てられており、その接続先となる $\neg x$ にはすでに「真」が割り当てられており、 $x$ に新たに「真」を割り当てるという状況に矛盾するからである。

また、新たに「偽」を割り当てられるリテラル（ $\neg x$ とする）に接続する経路上には、すでに「真」を割り当てたリテラルが存在しないことも言える。なぜなら先ほどの構成方法より、「真」を割り当てたリテラルから接続する経路上のリテラルは、すべて「真」が割り当て済みになっているからである。

以上より、先と同じ操作を何度も繰り返すことが可能であることが分かり、最終的にすべてのリテラルに矛盾なく真偽値が割り当てられることになる。

問2.5(2)

問2.5(1)で与えたアルゴリズムは、多項式時間で処理できる。

（参考）Where Can We Draw The Line? - On the Hardness of Satisfiability Problems [PDF]

問2.6

変数 $(P_1,\,\cdots,\,P_n)$ を持つ任意の命題論理式 $\varphi$ を考える。 ${\rm SAT}(\varphi) = 1$ の場合、 $P_1$ を 0, 1 に固定して得られる論理式をそれぞれ $\varphi_0,\,\varphi_1$ として、 ${\rm SAT}(\varphi_0)$ か ${\rm SAT}(\varphi_1)$ の少なくとも一方は 1 になる。（さもなくば、 ${\rm SAT}(\varphi) = 1$ に矛盾する。）

1 になった論理式を任意に選択して（選択したものを ${\rm SAT}(\varphi_{x_1})$ とする）、この中に含まれる $P_2$ を 0, 1 に固定して得られる論理式を $\varphi_{x_1,0},\,\varphi_{x_1,1}$ とすると、先ほどと同様に ${\rm SAT}(\varphi_{x_1,0}),\,{\rm SAT}(\varphi_{x_1,1})$ の少なくとも一方は 1 になる。（さもなくば、 ${\rm SAT}(\varphi_{x_1}) = 1$ に矛盾する。）

以下同様の議論を繰り返すと、 ${\rm SAT}(\varphi_{x_1,x_2,\cdots,x_n}) = 1$ となる（つまり、 $\varphi$ を充足する） $(P_1,\,\cdots,\,P_n)$ の組 $(x_1,\,\cdots,\,x_n)$ が得られる。この過程では、 $2n$ 回の判定問題 ${\rm SAT}$ を解いているので、全体の計算は多項式時間で実施できる。

問2.7

次の手続きで判定問題 TIME-EVAL を解いていく。

まず、与えられた機械 M に対応する、t 遷移分の回路を作成する。これは、多項式時間で可能。（ ${\rm _{MAKE}C_{IRC}}\in {\rm FP}$ ）

続いて、この回路を順次評価していき t 遷移以内に受理されるかを判定する。各遷移の評価は、多項式時間で可能（ ${\rm _CE_{VAL}}\in {\rm P}$ ）なので、t 遷移分の評価も多項式時間で行うことができる。

問2.8

十分性を示す。

$x$ が与えられた際、仮定より、回路 $C_n\,\,\,(n=|x|)$ を多項式時間で作成できる。また、多項式時間で作成した回路なので、そのステップ数は多項式で抑えられる。したがって、この回路で $x$ を評価して $A(x)$ を得る処理は多項式時間で実施できる。（ $\rm{_CE_{VAL}} \in P$ に注意。）

必要性を示す。

判定問題 A が P に属する場合、その定義より、多項式 $\tau(|x|) = O(|x|^k)$ が存在して、 $\tau$ 時間限定で問題 A を解く機械 M が存在する。ここで、任意の n が与えられた際に、長さ n の入力 x に対する機械 M の処理は、高々 $\tau(n)$ の時間で完了するので、この処理を再現する（高々 $\tau(n)$ ステップの）回路は多項式時間で作成できる。（ ${\rm _{MAKE}C_{IRC}} \in FP$ に注意。）この回路が $C_n$ に他ならない。

問2.9(1)

判定問題 $D_{\exp}$ の定義：「 $M$ に $(M,\,0^k)$ を入力すると消費時間 $2^k$ 以内に受理しない」

$D_{\rm \exp} \in {\rm P}$ と仮定すると、この問題を多項式時間で解く機械 $M_{\rm \exp}$ が存在する。

この時、ある $k$ について、 $D_{\rm \exp}(M_{\rm \exp},\,0^k) = 1$ だとすると、 $D_{\rm \exp}$ の定義より、「 $M_{\rm \exp}$ に $(M_{\rm \exp},\,0^k)$ を入力すると消費時間 $2^k$ 以内に受理しない」ことを意味する。一方、 $M_{\rm \exp}$ の定義より、 $M_{\rm \exp}(M_{\rm \exp},\,0^k) = 1$ でなければならない。これは、 $M_{\rm \exp}(M_{\rm \exp},\,0^k)$ が多項式時間以内に受理されており、 $D_{\rm \exp}$ の定義と矛盾する。

あるいは、 $D_{\rm \exp}(M_{\rm \exp},\,0^k) = 0$ だとすると、 $D_{\rm \exp}$ の定義より、「 $M_{\rm \exp}$ に $(M_{\rm \exp},\,0^k)$ を入力すると消費時間 $2^k$ 以内に受理する」ことを意味する。一方、 $M_{\rm \exp}$ の定義より、 $M_{\rm \exp}(M_{\rm \exp},\,0^k) = 0$ でなければならない。これは、 $M_{\rm \exp}(M_{\rm \exp},\,0^k)$ が受理されておらず、 $D_{\rm \exp}$ の定義と矛盾する。

したがって、最初の仮定 $D_{\rm \exp} \in {\rm P}$ は誤っている。

問2.9(2)

$y = (M,\,0^k)$ として、 $D_{\exp}(y)$ の答えは、TIME-EVAL に $x = (M,\,(M,\,0^k),\,0^{2^k})$ を入力すると得られる。（正確には、TIME-EVAL の結果の否定が答え。）

TIME-EVAL は P に属することから、この計算時間 $\tau$ は、入力 $|x|$ の多項式で抑えられる。つまり、 $\exists n;\,\tau = O(|x|^n)$ 。

ここで、 $|x|=|M|+|M|+k+2^k=O(2^{|y|})$ より、 $\tau = O(2^{n|y|})$ 。つまり、 $D_{\exp}(y)$ の答えは $|y|$ の指数時間で得られることが分かる。

問2.10

PSPACE に属する判定問題を解く機械 M は、ある $k$ を用いて $\sigma(n)=O(n^k)$ として、 $\sigma$ 空間限定となる。この機械の時点表示 $ID_{M,|x|,\sigma(|x|)}$ の元の個数 $I$ を考えると、

$I=|Q|\cdot(|x|+1)\cdot\sigma(|x|)^k\cdot|\Gamma|^{k\sigma(|x|)}=O(|x|^{2k+1}|\Gamma|^{k|x|^k})=O(|\Gamma|^{|x|^{k+1}})$

となる。この機械 M の実行時間は、上記の時点表示の元の個数で抑えられるので、M は、EXP に属する。

問2.11

$f,\,g\in{\rm FL}$ を計算する機械をそれぞれ $M_f,\,M_g$ として、これらを修正・結合した次のような機械を構成する。

まず、 $M_g$ に「作業用テープ1（利用する長さは最大 $\log(|g(x)|)$ ）」と「作業用テープ2（利用する長さは最大1）」を追加して、作業用テープ1に記載された値nを読み取り、 $g(x)$ のnビット目の値を作業用テープ2に書き出す機械 $M_{g'}$ に修正する。（ $M_g$ がもともと出力用テープに書き出していた内容は、何も書き出さずに捨てて、nビット目だけを作業用テープ2に書き出すように修正する。）

この機械に、 $M_f$ の入力テープ読み取り処理を次のように修正した機械を結合する。 $M_f$ が入力テープの n ビット目を読み取る必要がある場合は、先ほどの作業用テープ1にnを記録して、 $M_{g'}$ の処理を呼び出す。そして、作業用テープ2に記録された値を利用する。

以上の機械により、 $f\circ g(x)$ が計算できる。 $g \in {\rm FL} \subseteq {\rm FP}$ より、 $|g(x)|$ は $|x|$ の多項式で抑えられるので、作業用テープ1の利用長は $\log(|x|)$ の多項式で抑えられる。したがって、この結合機械は、 $\rm{FL}$ に属する。

問2.12(1)

「複数の2進数の和のひっ算」を対数空間限定のアルゴリズムで実装する。

$k$ 個の非負整数 $x_1,\,\cdots,\,x_k$ がそれぞれ2進数で入力テープに記録されているとして、 $l = \max_i|x_i|$ と置く。この時の入力の長さは、 $k \times l$ 以下であるので、これから作るアルゴリズムの消費空間が $O(\log(k \times l)) = O(\max\{\log k,\,\log l\})$ で抑えられていればよい。

まず、任意の自然数 $(n, m)\,\,\,(n \leq l,\,m \leq \log k)$ について、「各入力値の下位からnビット目を合計した値の下位からmビット目の値を求める」という計算は、対数空間限定で実施できる。これは、次のアルゴリズムを実装すればよい。

各入力値について下位からnビット目を順次読み取り、それまでの合計を作業用テープ1に記録していく。作業用テープ1の長さは $\log k$ で抑えられる。作業用テープ1に記録された結果の下位からmビット目が求める値である。

次に、任意のjについて、問題の答（入力値の和）の下位からjビット目の値は、次のアルゴリズムで求められる。まず、各入力値の下位からjビット目を順次読み取り、それまでの合計の下位1ビットを作業用テープ2（最大長1）に記録していく。次に、各入力値の下位から(j-1)ビット目の合計の下位から2ビット目を前述の計算で求めて、それを作業用テープ2の値と合計して、その下位1ビットを作業用テープ2に上書きする。

この後、一般に、「各入力値の下位から(j-i)ビット目の合計の下位から(i+1)ビット目を求めて、作業用テープ2の値と合計して、その下位1ビットを作業用テープ2に上書きする」という処理を i=1,2,...,(j-1) について繰り返せば、最終的に作業用テープ2に記録された値が求める値である。このループ処理のインデックスとして使う作業用テープの長さは、 $\log l$ で抑えられる。

以上のアルゴリズムで使用した作業用テープの長さは、すべて $O(\log(k \times l)) = O(\max\{\log k,\,\log l\})$ で抑えられていたので、これで、対数空間限定で答を求めるアルゴリズムが見つかった。

問2.12(2)

「2進数の積のひっ算」を対数空間限定のアルゴリズムで実装する。ここでは、 $a \times b$ を計算するものとする。また、一般に、２進数 $x$ の下位からiビット目を $x_i$ と表記する。（iが $x$ のビット数より大きい場合は0とする。）

この時、 $a \times b$ の下位からkビット目は、次の対数空間限定のアルゴリズムで計算できる。

まずはじめに、

$(a_k \times b_1) + (a_{k-1} \times b_2) + \cdots = \sum_{i=0}^{k-1}(a_{k-i} \times b_{i+1})$

の最下位ビットを求める。問2.12(1)の和を求めるアルゴリズムと同様に、長さ1の作業用テープにそれまでの合計の最下位ビットを記録していけば、これは、対数空間限定で処理できる。

次のこの値に１つ下のビットからの繰り上がりを足す。つまり、

$\sum_{i=0}^{(k-1)-1}(a_{k-i} \times b_{i+1})$

の下から2ビット目の値を足す。上記の和は、0か1を $k-1$ 個足しているだけなので、最大でも $k-1$ であり、値そのものを長さ $\log k$ の作業用テープに記録しても構わない。

以下同様に、

$\sum_{i=0}^{(k-j)-1}(a_{k-i} \times b_{i+1})$

の下から $j+1$ ビット目の値を足す処理を $j=1,\,\cdots,\,(k-1)$ で繰り返せば良い。

問2.13

補題1：任意の $a,\,b>0$ について、 $\log(a+b+1) \geq \min(\log a,\,\log b)+1$

（証明）一般性を失わずに $a \leq b$ と仮定できる。この時、左辺を $X$ 、右辺を $Y$ とすると、

$2^X=a+b+1 \geq 2a+1$

$2^Y=2^{(\log a)+1}=2a$

（証明終わり）

命題論理式 $\varphi$ の値は、 $\log |\varphi|$ 以下の記憶域（作業用テープ）で計算できることを木の高さについての帰納法で証明する。

木の高さが2（葉が2つ）の場合は、左の葉の値を記憶しておき、右の葉の値を読み取れば、答が決まる。つまり、記憶域は、 $1 = \log2$ で計算できる。

木の高さがk以下の場合に成立するとして、高さが k+1 の命題論理式 $\varphi$ を考える。 $\varphi$ の頂点から見て、左右の部分木を $\varphi_L,\,\varphi_R$ とすると、次の関係が成り立つ。

$|\varphi| = |\varphi_L|+|\varphi_R|+1$ ---(1)

$\log|\varphi| \geq \min(\log|\varphi_L|,\,\log|\varphi_R|)+1$ ---(2) （∵補題1）

問2.14

次の3本の作業用テープを用意する。

・ $\forall$ が前置された変数が取りうる値の組をカウントする作業用テープ1（長さは k 以下）

・ $\exists$ が前置された変数が取りうる値の組をカウントする作業用テープ2（長さは k 以下）

・フラグ用の作業用テープ3（長さ 1）

次の2重ループを実施する。

=============
[作業用テープ1をインクリメントするループ]
｜
｜作業用テープ3に0を記録する
｜
｜ [作業用テープ2をインクリメントするループ]
｜｜
｜｜作業用テープ1の内容を $\forall$ が前置された変数に、
｜｜作業用テープ2の内容を $\exists$ が前置された変数にそれぞれ
｜｜割り当てて、真になったら、作業用テープ3に1を記録する(*)
｜｜
｜｜ $\exists$ が前置された変数がすべて1であればループを終了する
｜
｜作業用テープ3の内容が0であれば、問題の答は「偽」（ここで機械を停止する）
｜
｜ $\forall$ が前置された変数がすべて1であればループを終了する

ループが終了すれば、問題の答は「真」（ここで機械を停止する）
=============

(*) 具体的な真偽値が与えられた論理式の真偽判定は、問2.13より、対数空間限定で計算可能。

以上で使用した作業用テープの長さの合計は、k の多項式で抑えられている。