§E18.10時間計算量と空間計算量

証明. 入力$1^n$を一度走査して$n$の二進表記を得る。この計数には$O(n)$時間と$O(\log(n+2))$空間を要する。$k$は固定されているため、二進整数の筆算による乗算を$k-1$回行えば$n^k$の二進表記を得る。各中間値のビット長は$O(\log(n+2))$であり、筆算時間は$O((\log(n+2))^2)$の固定定数倍である。したがって全時間は

であり、$\max\{1,n^k\}$は時間構成可能である。$n=0$の場合には有限制御から$1$を出力する。

空間構成可能性を示す。作業テープを一本だけ用い、初期ヘッド位置を位置$0$とする。固定した$k$に対し、二進整数$n$、$n^k$、および$n^k-n$の計算と反復管理に必要なマス数は$c_k\lceil\log_2(n+2)\rceil$以下であるような定数$c_k$が存在する。したがって、ある整数$N_k\ge2$を選ぶと、すべての$n\ge N_k$について

となる。$k$は固定されているため、必要な固定個数の二進レジスタは、有限個のトラックをもつ一つのテープアルファベットによって実装することができる。

最初に、入力長が$N_k$未満であるかを有限制御で調べる。この判定中は作業ヘッドを初期位置$0$から動かさない。$n<N_k$ならば、有限制御は入力長$n$を状態に保持しているので、状態列へ組み込んだ$\max\{1,n^k\}-1$回の右移動を実行して停止する。この分岐が訪れる作業マスは

だけである。特に$n=0$と$n=1$では右へ動かず、初期位置$0$だけを訪れる。この処理は有限個の入力長ごとに有限個の状態を固定したものであり、追加の作業マスを使用しない。

$n\ge N_k$ならば、入力ヘッドを左端へ戻し、入力を再走査する。最初の$1$には既に訪れている作業位置$0$を対応させ、二文字目以後の各$1$を読むたびに作業ヘッドを一マス右へ動かす。走査後に訪問済みの作業マスはちょうど

であり、位置$n-1$に右端印を置く。入力をもう一度走査して$n$を二進レジスタへ記録し、固定回数の二進乗算と減算によって$r=n^k-n$を計算する。上の$N_k$の選び方により、これらのレジスタと演算用の印はすべて$I_n$の内部に収まり、右端印の外側を訪れない。

$r>0$の間、機械は$I_n$内の二進レジスタで$r$を一つ減らし、現在の右端印まで訪問済み領域を走査する。次に、右端印を一マス右の未訪問マスへ移し、左端のレジスタへ戻る。一回の反復で新しく訪れる作業マスは、右端印の移動先の一マスだけである。この反復を$n^k-n$回実行するので、停止時の訪問マス集合は

であり、その個数は厳密に$n^k$である。初期計数、二進算術、残数管理、および右端までの往復は、いずれも現在の右端より外側を訪れない。以上により、すべての$n$で$\max\{1,n^k\}$個の作業マスだけを訪れて停止する機械が得られる。

$\lceil\log_2(n+2)\rceil$については、初期値$1$の二進カウンタへ入力の各$1$に対して一を加える。最終値は$n+1$であり、その二進表記の桁数は

である。桁が増えるときだけ新しい一マスを訪れるようにすれば、ちょうど指定個数のマスを訪れて停止する。▨

証明.主張 (1)を示す。配置は、現在の状態、入力ヘッドの位置、各作業テープの内容、および各作業テープのヘッド位置の組である。状態は$|Q|$通りである。入力ヘッドの位置は$0$から$n$までの$n+1$通りである。訪問済み領域が$b$マス以下である作業テープの内容は、位置$0$から$b-1$までの記号列によって定まり（それ以外のマスは空白記号である）、$|\Gamma|^b$通り以下である。各作業テープのヘッド位置は$0$から$b$までの$b+1$通り以下である。したがって配置の個数は

以下である。この個数の二進対数は

である。仮定$b\ge\lceil\log_2(n+1)\rceil$から$\log_2(n+1)\le b$であり、$b+1\le 2^{b+1}$から$\log_2(b+1)\le b+1$である。よって上の値は

以下である。そこで

と置く。$\log_2|Q|\ge 0$と$k\ge 1$から$c\ge 2$であり、$c$は正の整数である。天井関数は値を減らさないので、配置の個数は$2^{c(b+1)}$以下である。この$c$は$|Q|$、$k$、$|\Gamma|$だけから定まり、$n$にも$b$にも依存しない。また$b$は非負整数であるから、$c(b+1)$は正の整数である。

主張 (2)を示す。仮定の下で、時刻$0,1,\ldots,2^{c(b+1)}$における配置を考える。これらは$2^{c(b+1)}+1$個あり、いずれも主張 (1)の条件を満たす配置である。主張 (1)により相異なる配置は$2^{c(b+1)}$個以下であるから、鳩の巣原理により、二つの相異なる時刻$t_1<t_2$で同じ配置が現れる。$M$は決定性機械であるから、同一の配置から始まる以後の計算は一致する。したがって、時刻$t_1$以後の配置列は周期$t_2-t_1$で反復し、時刻$t_1$から$t_2-1$までに現れた配置以外の配置は現れない。仮定によりこれらの配置は停止状態を含まないので、$M$は$x$上で停止しない。▨

証明.$L\in\mathsf{DTIME}(t)$とし、$T_M(n)=O(t(n))$を満たす$L$の決定器$M$をとる。$M$の作業テープの本数を$k$とする。一遷移で各作業テープのヘッドは高々一マスしか動かないので、初期位置を含めて、入力$x$上で訪れる作業マスの総数は

を満たす。長さ$n$の入力全体で最大値をとれば$S_M(n)\le k(T_M(n)+1)$である。$T_M(n)=O(t(n))$から、定数$C>0$と$n_0$が存在して$n\ge n_0$で$T_M(n)\le Ct(n)$であり、$t(n)\ge 1$とあわせて

を得る。したがって$S_M(n)=O(t(n))$である。$M$は$L$の決定器であるから$L\in\mathsf{DSPACE}(t)$である。▨

証明.$S_M(n)=O(s(n))$を満たす$L$の決定器$M$をとる。定数$C>0$と$n_0$が存在して、$n\ge n_0$で$S_M(n)\le Cs(n)$である。$n<n_0$を満たす$n$は有限個であり、そのような各$n$について$S_M(n)$は有限の値である。$s(n)\ge 1$であるから、

と置けば、すべての$n$について$S_M(n)\le C's(n)$である。$C'$は正の整数としてよい。

入力$x$の長さを$n$とし、$b=C's(n)$と置く。$M$が$x$上で訪れる作業マスの総数は$\sigma_M(x)\le S_M(n)\le b$であるから、各作業テープの訪問済み領域は計算の全時点で$b$マス以下である。また$b\ge s(n)\ge\lceil\log_2(n+1)\rceil$である。よって補題 3.2を適用することができる。同補題の定数を$c$とする。$M$は決定器であるから$x$上で停止する。補題 3.2 (2)の対偶により、$M$が$x$上で行う遷移数は$2^{c(b+1)}$未満である。$C'\ge 1$から$b+1=C's(n)+1\le C'(s(n)+1)$であり、

である。右辺は$n$だけで定まるので、長さ$n$の入力全体で最大値をとって

を得る。$\gamma$を$cC'$以上の正の整数とすれば$T_M(n)\le 2^{\gamma(s(n)+1)}$であり、とくに$T_M(n)=O(2^{\gamma(s(n)+1)})$である。関数$n\mapsto 2^{\gamma(s(n)+1)}$は$\mathbb N$から$\mathbb N$への関数であるから、$L\in\mathsf{DTIME}(2^{\gamma(s(n)+1)})$である。▨

証明.$O$記法では有限個の$n$における値を無視するので、$n\ge 1$で一致する二つの関数から同じクラスが定められる。とくに、各$k\ge 1$について

である。

最初に$\mathsf L\subseteq\mathsf P$を示す。$s(n)=\lceil\log_2(n+2)\rceil$と置く。$n+2\ge 2$から$s(n)\ge 1$であり、$n+2>n+1$から$s(n)\ge\lceil\log_2(n+1)\rceil$である。よって命題 3.4を適用することができ、$L\in\mathsf L$に対して正の整数$\gamma$が存在して$L\in\mathsf{DTIME}(2^{\gamma(s(n)+1)})$である。ここで$s(n)<\log_2(n+2)+1$であるから

であり、$n\ge 1$では$n+2\le 3n$なので

である。したがって$L$の決定器の最悪時間は$O(n^{\gamma})$であり、$L\in\mathsf{DTIME}(n^{\gamma})\subseteq\mathsf P$である。

次に$\mathsf P\subseteq\mathsf{PSPACE}$を示す。$L\in\mathsf P$とすると、ある$k\ge 1$について$L\in\mathsf{DTIME}(n^k)=\mathsf{DTIME}(\max\{1,n^k\})$である。関数$\max\{1,n^k\}$はすべての$n$で$1$以上であるから、命題 3.3により

である。▨

証明. 各作業テープの有限な使用部分を、区切り記号を用いて

と一本の作業テープ上に符号化する。各$u_i$では、走査中の一文字だけに印を付ける。まだ訪れていない右側のマスは明示せず、ヘッドが右端を越えるときに空白記号を一つ挿入する。$k$とテープアルファベットは機械ごとに固定された有限集合である。

元の配置で訪問済みの作業マスが合計$\sigma'$個であるとき、符号の長さは$\sigma'+O(k)$である。$U$は符号を左から右へ走査し、$k$個の印付き記号を有限制御に記録する。入力テープの走査記号とこれらの記号から、$M$の次の状態、各書込み記号、および各ヘッドの移動方向を決定する。次の往復走査で書込みと印の移動を行う。右端への空白挿入が必要な場合には、右側の有限符号を一マスずつ移す。この移動も符号長に比例する時間で終わる。

したがって、$M$の一段を模倣する時間は$O(\sigma'+1)\le O(\sigma+1)$であり、$\tau$段全体は$O(\tau(\sigma+1)+1)$時間で終わる。初期符号は各作業テープの左端空白を表す定数長の語であり、入力は別の読取り専用テープに残るので、初期化に入力全体の複写は要らない。

各模倣段の後の符号が$M$の対応する配置を表すことは、模倣段数に関する帰納法で従う。したがって、$U$は$M$と同じ時点に対応する符号で同じ受理状態または拒否状態へ移る。符号が占めるマス数は、訪問済み作業マス数に区切りと印の定数倍を加えた$O(\sigma+1)$である。

最後に、固定本数の各作業テープでは、一段につき高々一つの新しいマスを訪れる。したがって$\sigma\le k(\tau+1)$であり、時間上界は$O((\tau+1)^2)$となる。▨

証明.$k$本の作業テープで時間$O(n^d)$を要する決定器へ定理 4.1を適用すると、一本の作業テープによる時間は

である。したがって、多テープで多項式時間なら単テープでも多項式時間である。逆向きの包含は、一本のテープを多テープ機械の第一作業テープとして使用する直接の模倣による。

空間について、同じ定理の符号は$O(s(n)+1)$マスしか使用しない。$O$記法では定数倍が吸収されるため、単テープと多テープで同じ$\mathsf{DSPACE}(s)$を得る。▨

証明.$f$の計算時間を$O(n^c)$とし、$B$の決定器の時間を入力長$m$に対して$O(m^d)$とする。出力を一文字書くには少なくとも一遷移を要するため、定数$C>0$が存在して

である。

入力$x$から最初に$f(x)$を計算し、その出力を$B$の決定器の入力として実行する。多テープによるこの合成の時間は

であり、多項式である。必要なら系 4.2によって一本の作業テープへ変換しても、多項式時間性は保たれる。受理条件は$x\in A$と$f(x)\in B$の同値によって正しい。▨