時間階層定理
Time hierarchy theorem
$ \textbf{DTIME}(f) \subsetneq \textbf{DTIME}(g)
Proof.
$ D(x) := \left\{ \begin{array}{ll} 1 & \text{if $U_{x,g(|x|)}(x) = 0$} \\ 0 & \text{otherwise} \end{array} \right.
とする。定義から$ D \in \textbf{DTIME}(g)
$ D \in \textbf{DTIME}(f)と仮定する。
TM$ M, $ cが存在して$ D(x) = 1 \iff M_{c f(|x|)} = 1が成り立つ
TMのエミュレーションは$ T \log Tで行えるのであるインデックス$ eが存在して
$ D(x) = 1 \iff U_{e, c' f(|x|)\log f(|x|)}(x) = 1
$ D(x) = 0 \iff U_{e, c' f(|x|)\log f(|x|)}(x) = 0
仮定よりある$ n_0が存在し$ \forall |x| > n_0について$ c' f(|x|) \log f(|x|) < g(|x|)となる
$ eをそのようにとる$ |e| > n_0
$ c' f(|e|) \log f(|e|) < g(|e|)より
$ D(e) = 1と仮定する
$ U_{e, c' f(|e|)\log f(|e|)}(e) = 1より$ U_{e,g(|e|)}(e) = 1
従って$ d(e) = 0
矛盾
$ D(e) = 0と仮定する
$ U_{e, c' f(|e|)\log f(|e|)}(e) = 0より$ U_{e,g(|e|)}(e) = 0
従って$ d(e) = 1
矛盾
よって$ D \notin \textbf{DTIME}(f) ❏ $ \textbf{NTIME}(f) \subsetneq \textbf{NTIME}(g)
NDTMで値の反転$ x \mapsto \neg xを定義するのは難しい
$ D(i) := \bigvee_p \neg N_i^p(i)
と素朴に定義すると値は反転しない
しかし決定性TMでは反転が定義できるのでこれを用いる。対数時間のエミュレーションを計算するため対数間隔の区間$ (r(i), r(i+1)] にインデックスを割り当てる
$ n <_o g(n)が必要?
Proof.
$ g'(x) := x^{-q}g(x)であり$ f(n+1) <_o g''(n+1) <_o g'(n) <_o g(n)を満たすと仮定する
$ r(1) := 2
$ r(n+1) := 2^{g'(r(n))}
$ x = 1^nから$ r(i) < n \le r(i + 1)となる$ iを計算したい
$ r^{-1}_i(1^n) := \text{if $\log(n) \le g'(r(i))$ then $i$ else $r^{-1}_{i+1}(1^n)$}
$ r^{-1}(1^n) := r^{-1}_0(1^n)
とおくとこれは$ rの逆関数で計算時間は$ O(r^{-1}(n)(n + g'(r(r^{-1}(1^n))))) < O(n^{1+q} +g(n))
$ rの定義より$ r^{-1}(n) <_o \log(n) <_o n^{q}より
$ qは任意に取れるので$ O(n+g(n))
lazy diagonalize (遅延対角化?)関数$ Dを次のように定義する
$ D(1^n) := \left\{ \begin{array}{ll} N_{i, g(n)}(1^{n+1}) & \text{if $r(i) < n < r(i+1)$ and $N_{i, g(n)}(1^{n+1}) \downarrow$} \\ 1 & \text{if $r(i) < n < r(i+1)$ and $N_{i, g(n)}(1^{n+1}) \uparrow$}\\ \neg M_{\ulcorner N_{i, g''(r(i)+1)}(1^{r(i)+1}) \urcorner}() & \text{if $n = r(i+1)$} \end{array} \right.
$ M_{\ulcorner N_{i, g(r(i)+1)}(1^{f(i)+1}) \urcorner}()は$ N_iの決定性TMによるエミュレーションを意味する
前二つの計算時間は$ O(n + g(n)+ g(n)) = O(n + g(n))
最後の計算時間は$ O(2^{g''(r(i)+1)}) < O(2^{g'(r(i))}) < O(g(2^{g'(r(i))})) = O(g(n))
よって計算時間は$ O(g)
$ D \in \textbf{NTIME}(f)と仮定する。$ D(1^n) = N_{e, f(n)}(1^n)とする
$ Dの定義より
$ r(e) < n < r(e+1)を満たす$ nについて
$ D(1^n) = N_{e,g(n)}(1^{n+1}) =D(1^{n+1})
従って
$ D(1^{r(e)+1}) = D(1^{r(e+1)})
一方
$ D(1^{r(e+1)}) = \neg M_{\ulcorner N_{e, g''(r(e)+1)}(1^{r(e)+1}) \urcorner}() = \neg M_{\ulcorner D(1^{r(e)+1}) \urcorner}() = \neg D(1^{r(e)+1})より
$ D(1^{r(e)+1}) \ne D(1^{r(e+1)})
参照