計算量理論

要点：状態、入力ヘッドの位置、各作業テープのヘッドの位置と最初の $S$ マスの内容を数える。

手続きは通常のプログラムの形で書く。その実行時間が $T$ なら、多テープの機械でも時間 $T$ の多項式の範囲で実行できる（P対NP問題 の定義の後の段落と同じ扱い）。
1：$L$ を空間 $c\,s(n)+c$ で判定する非決定性の機械 $M$ をとる。入力 $w$ の初期様相から遷移で到達できる様相は、どれもある計算の道の上にあるので、使ったマスが $c\,s(n)+c$ 以下であり、lem-cc-configurations により $N\le2^{d\,s(n)}$ 個以下である。各様相は $O(s(n))$ 個の記号で書ける（入力ヘッドの位置は $\log(n+2)=O(s(n))$ 桁）。到達できる様相の集合 $R$ を、初期様相だけから始め、「$R$ の元から 1 回の遷移で移れる様相で $R$ にないもの」を加えることを、加えるものがなくなるまで繰り返して求める（幅優先探索 と同じ考え方）。繰り返しは $N$ 回以下で、1 回は $O(N^2s(n))$ 程度の比較で済むので、全体の時間は $N$ の多項式、すなわちある $d'$ について $2^{d's(n)}$ 以下である。$R$ に受理状態の様相があれば受理し、なければ拒否する。これは $L$ を判定する決定性の手続きである。
2：決定性の機械は非決定性の機械の特別な場合なので、$\mathrm{L}\subset\mathrm{NL}$、$\mathrm{P}\subset\mathrm{NP}$、$\mathrm{PSPACE}\subset\mathrm{NPSPACE}$ である。1 を $s(n)=\log n$ に使うと $2^{d\log n}$ は $n$ の多項式で押さえられるので $\mathrm{NL}\subset\mathrm{P}$、$s(n)=n^c$ に使うと $\mathrm{NPSPACE}\subset\mathrm{EXP}$ である。
$\mathrm{NP}\subset\mathrm{PSPACE}$ を示す。$L$ を時間 $t(n):=c\,n^c+c$ で判定する非決定性の機械 $M$ をとり、各様相で適用できる遷移の数の上限を $r$ とする。$M$ の道は、各段でどの遷移を選んだかを表す $\{1,\dots,r\}$ の長さ $t(n)$ 以下の列で決まる。決定性の機械は、この列を辞書式の順に 1 つずつ作業テープに書き、その列に従って $M$ の計算をたどり、$q_{\mathrm{acc}}$ に達する列があれば受理する。列とたどる計算の様相は $O(t(n))$ 個のマスに収まり（$t(n)$ 段で使えるマスは各テープ $t(n)+1$ 個以下）、次の列に移るときに同じマスを使い直すので、空間は $O(n^c)$ である。$\square$

段 1（様相のグラフ）。$L$ を空間 $c\,s(n)+c$ で判定する非決定性の機械 $M$ をとる。入力 $w$（長さ $n$）を固定し、使ったマスが $S:=c\,s(n)+c$ 以下の様相を頂点とし、1 回の遷移で移れる様相の組を辺とする有向グラフ $G$ を考える。lem-cc-configurations により頂点は $2^m$ 個以下である（$m:=d\,s(n)$）。各様相は $O(s(n))$ 個の記号で書け、2 つの様相の間に辺があるかは $M$ の遷移の表と照らして空間 $O(s(n))$ で判定できる。
段 2（到達の判定）。様相 $C,C'$ と $i\ge0$ について、$G$ に $C$ から $C'$ への長さ $2^i$ 以下の道があるかを返す手続き $\mathrm{REACH}(C,C',i)$ を次で定める。

• $i=0$ なら、$C=C'$ か、$C$ から $C'$ へ辺があるかを調べて返す。
• $i\ge1$ なら、頂点 $Z$ をすべて順に試し、$\mathrm{REACH}(C,Z,i-1)$ と $\mathrm{REACH}(Z,C',i-1)$ がともに真になる $Z$ があれば真を、なければ偽を返す。
  $i$ についての帰納法で、これが正しい答えを返すことを示す。$i=0$ は定義どおりである。長さ $\ell\le2^i$ の道 $C=Y_0,Y_1,\dots,Y_\ell=C'$ があれば、$Z:=Y_{\lfloor\ell/2\rfloor}$ で前半と後半の長さはどちらも $2^{i-1}$ 以下であり、帰納法の仮定から 2 つの呼び出しは真を返す。逆に 2 つが真なら、長さ $2^{i-1}$ 以下の道をつないで長さ $2^i$ 以下の道ができる。
  段 3（空間）。$\mathrm{REACH}$ を、呼び出しごとに $(C,C',i,Z)$ と「いまどちらの呼び出しを実行中か」を 1 段として積み上げるスタックで実行する。1 段は $O(s(n))$ 個のマスに収まり（$i\le m=O(s(n))$ も 2 進法で $O(\log s(n))$ 桁）、呼び出しは $i$ が 1 つずつ減るので、スタックの高さは $m+1$ 以下である。1 つの呼び出しが終われば、その段のマスは次の $Z$ や次の呼び出しで使い直す。よって空間は $O(s(n)\cdot m)=O(s(n)^2)$ である。
  段 4（判定の手続き）。空間構成可能性により $s(n)$ を空間 $O(s(n))$ で求め、$S$ と $m$ を定める。受理状態をもつ様相 $C_{\mathrm{acc}}$（使ったマスが $S$ 以下のもの）を順にすべて試し、初期様相 $C_0$ について $\mathrm{REACH}(C_0,C_{\mathrm{acc}},m)$ が真になるものがあれば受理し、なければ拒否する。$M$ が $w$ を受理する道があれば、同じ様相を 2 度通る部分を取り除くと、長さが頂点の数 $2^m$ 未満の道になるので、この手続きは受理する。逆に受理すれば、$C_0$ から受理状態の様相に至る道があり、それは $M$ の受理する道である。手続きは決定性で、どの入力でも停止し、空間 $O(s(n)^2)$ で動く。$\square$

1：$\mathrm{NSPACE}(n^c)\subset\mathrm{DSPACE}(n^{2c})\subset\mathrm{PSPACE}$ と、thm-cc-inclusions の $\mathrm{PSPACE}\subset\mathrm{NPSPACE}$ による。2：thm-cc-savitch を $s(n)=\log n$、$s(n)=n$ に使う。$\square$

要点：線形有界オートマトンの様相は $2^{O(n)}$ 個なので、段数を 2 進法で数えて打ち切れば、すべての道が停止する機械になる。

要点：$M_\alpha$ のすべてのテープの内容を $U$ の 1 本の作業テープにマスごとの組として並べ、$M_\alpha$ の 1 段を、そのテープの定数回の往復で模倣する。往復 1 回の段数は、使っている長さ $O(T+\lvert x\rvert)$ に比例する。

段 1（包含）。$f\le f^2$ で $f^2/g\to0$ なので、十分大きな $n$ で $f(n)\le g(n)$ であり、$\mathrm{DTIME}(f)\subset\mathrm{DTIME}(g)$ である。
段 2（反転する機械）。決定性の機械 $D$ を次で定める。入力 $x$（長さ $n$）に対し、

1. $1^{g(n)}$ を時計のテープに書き、そのヘッドを右端に置く（時間構成可能性により時間 $O(g(n))$）。
2. 組 $(x,x)$ を表す語を作業テープに書き（時間 $O(n)$）、それを入力テープとみなして $U$ を実行し、$U$ の 1 段ごとに時計のヘッドを 1 つ左へ動かす（2 つは同じ段で行える）。
3. 時計が尽きる前に $U$ が停止して答え $b$ を返したら、$b$ と逆の答え（受理なら拒否、拒否なら受理）を返す。時計が尽きたら拒否する。
   $D$ はどの入力でも時間 $O(n+g(n))=O(g(n))$ で停止するので、$D$ の判定する言語 $L_D$ は $\mathrm{DTIME}(g)$ に属する。
   段 3（$L_D\notin\mathrm{DTIME}(f)$）。$L_D$ を時間 $c\,f(n)+c$ で判定する決定性の機械 $M$ があったとする。$n\ge1$ では $f(n)\ge1$ なので $c\,f(n)+c\le2c\,f(n)$ である。$M$ を表す語 $\alpha$ のどれについても $C_\alpha$ は同じ値 $C_M$ であり、$f^2/g\to0$ から、ある $n_0\ge1$ があって $n\ge n_0$ なら $C_M(2c\,f(n)+2n)^2< g(n)$ である（$f(n)\ge n$ により左辺は $C_M(2c+2)^2f(n)^2$ 以下）。$M$ は無限に多くの語で表されるので、$M=M_\alpha$ かつ $\lvert\alpha\rvert\ge n_0$ となる $\alpha$ がとれる。入力 $x=\alpha$ では、$n:=\lvert\alpha\rvert$ として lem-cc-universal を $T=2c\,f(n)$、$\lvert\alpha\rvert+\lvert x\rvert=2n$ で使うと、$U$ は $(\alpha,\alpha)$ で $g(\lvert\alpha\rvert)$ 段より前に停止し、$M$ の入力 $\alpha$ での答えを返す。$D$ はその逆を返すので、$\alpha\in L_D$ と「$M$ が $\alpha$ を受理する」ことが食い違う。これは $M$ が $L_D$ を判定することに反する。$\square$

各 $c$ について、定数 $c'$ を十分大きくとればすべての $n$ で $c\,n^c+c\le c'\,2^n+c'$ となるので $\mathrm{P}\subset\mathrm{DTIME}(2^n)$ である。$f(n)=2^n$、$g(n)=2^{3n}$ は thm-cc-time-hierarchy の条件を満たす（$f^2/g=2^{-n}$）ので、$\mathrm{DTIME}(2^{3n})$ に属し $\mathrm{DTIME}(2^n)$ に属さない言語がある。それは $\mathrm{EXP}$ に属し $\mathrm{P}$ に属さない。$\square$