はじめに
知っている複雑性クラスを思い浮かべてください。
P, NP, NP完全, NP困難, あとCo-NPとかはご存じの方も多いでしょう。
今挙げた5つのクラスは、すべて時間によって定義されたクラスです。DTMで多項式時間で解ければPとかね。
しかし、いくら高速なアルゴリズムでも、メモリを無限に食ったら計算できないわけですから、そこらへんも重要だよね。という話です。
このシリーズの他の記事は、「計算複雑性理論」カテゴリーから飛んでください。
スマホの方は画面右下の「サイドバー」ボタンから、それ以外の方は画面右側のサイドバーから。
クラスの族
以下に示す２つは、厳密にはクラス（集合）ではなく、集合のあつまり（集合族）です1。
カッコの中の関数それぞれがクラスです。
なお、本記事内では、$n$は入力サイズです。
DSPACE
$\textrm{DSPACE}(f(n))$とは、決定性チューリングマシンを用いて、$O(f(n))$の空間で解ける問題のクラス（の族）です。
ここでいう空間サイズとは、チューリングマシンのテープ長のことです。
わかりづらいかもしれませんが、$f(n)$それぞれについてクラスが存在すると思ってください。
例えば、$\textrm{DSPACE}(n)$は、$O(n)$のテープ長があれば解ける問題のクラスとなります。
NSPACE
$\textrm{NSPACE}(f(n))$とは、非決定性チューリングマシンを用いて、$O(f(n))$の空間で解ける問題のクラス（の族）です。
$\textrm{DSPACE}$の非決定性バージョンですね。
決定性チューリングマシンで$f(n)$の空間を使って解けるなら、当然非決定性チューリングマシンでも$f(n)$の空間を使えば解けます。
つまり、$\textrm{DSPACE}(f(n))\subseteq \textrm{NSPACE}(f(n))$です。
クラス
PSPACE
クラス$\textrm{P}$の空間版みたいなのが$\textrm{PSPACE}$です。
入力サイズ$n$の多項式$p(n)$について、決定性チューリングマシンのテープ長が$O(p(n))$だけあれば解ける問題のクラスが$\textrm{PSPACE}$です。
$\textrm{DSPACE}$を用いて定義すると、
\begin{equation*}
\textrm{PSPACE}=\bigcup_{k\in \mathbb{N}}\textrm{DSPACE}(n^{k})
\end{equation*}
です。
Pは、多項式$O(p(n))$の時間で解ける問題のクラスでしたが、$p(n)$時間では、すべてのステップを一方向へ動いたとしても、当然$p(n)$個離れたセルまでしか移動できないので、$\textrm{P}\subseteq \textrm{PSPACE}$です。
NPSPACE
クラス$\textrm{P}$の空間版みたいなのが$\textrm{NPSPACE}$です。
入力サイズ$n$の多項式$p(n)$について、非決定性チューリングマシンのテープ長が$O(p(n))$だけあれば解ける問題のクラスがPSPACEです。
$\textrm{NSPACE}$を用いて定義すると、
\begin{equation*}
\textrm{NPSPACE}=\bigcup_{k\in \mathbb{N}}\textrm{NSPACE}(n^{k})
\end{equation*}
となります。
$\textrm{DSPACE}$と$\textrm{NSPACE}$の関係から、$\textrm{PSPACE}\subseteq \textrm{NPSPACE}$であることが直ちにわかります。
しかし、$\textrm{PSPACE}=\textrm{NPSPACE}$であることが証明されています（サヴィッチの定理の系）。
L
対数領域、つまり、$O(\log n)$の領域を持つ決定性チューリングマシンで解ける問題のクラス。
$\textrm{DSPACE}$を用いて定義すると、
\begin{equation*}
\textrm{L}=\textrm{DSPACE}(\log n)
\end{equation*}
です。
$n$が十分大きいとき、$\log n < n^{k}$が成り立つので$(k\in\mathbb{N})$、$\textrm{L}\subseteq\textrm{PSPACE}$です。
また、$O(\log n)$のテープ長を考えると、チューリングマシンのテープの異なる状態の数は、記号の種類$x\in \mathbb{N}$と、対数の底の変換公式を用いて、
\begin{equation*}
x^{O(\log n)}=n^{O(1)}
\end{equation*}
となり、さらにそれぞれの状態に対してヘッドの位置が$O(\log n)$個あるので、
\begin{equation*}
O(\log n)\cdot n^{O(1)}<O(n)\cdot n^{O(1)}=n^{O(1)}
\end{equation*}
となります2。
異なる状態数が多項式なら、同じ状態に２度到達する意味はないので、対数領域を持つチューリングマシンは多項式時間で動作を終了します。
よって、$\textrm{L}\subseteq\textrm{P}$です。
NL
対数領域、つまり、$O(\log n)$の領域を持つ非決定性チューリングマシンで解ける問題のクラス。
$\textrm{NSPACE}$を用いて定義すると、
\begin{equation*}
\textrm{NL}=\textrm{NSPACE}(\log n)
\end{equation*}
となります。
決定性チューリングマシンを用いて対数領域で解けるなら、当然非決定性チューリングマシンでも可能なので、$\textrm{L}\subseteq\textrm{NL}$です。
なお、$\textrm{NL}\subseteq\textrm{P}$です。
これも、サヴィッチの定理から導くことができます。すげぇ。
まとめ
\begin{equation*}
\textrm{L}\subseteq\textrm{NL}\subseteq\textrm{P}\subseteq\textrm{PSPACE}=\textrm{NPSPACE}
\end{equation*}
です。
コメント