「時間計算量」と「空間計算量」

以前、次のように書きました。

「複雑なものを理解するのには、長い時間と膨大な知識の集積が必要である」と。

それは、人間の認識の歴史について語ったものでしたが、具体的な計算の複雑さの尺度にも、この「長い時間と膨大な知識の集積」に対応する量があります。

それは、「その計算にどれぐらいの時間が必要か？」という時間の尺度と、「その計算にどのくらいのメモリー空間が必要か？」という空間の尺度です。前者を「時間計算量」、後者を「空間計算量」と言います。

チューリングマシンで言えば、「時間計算量」はある計算に必要なチューリングマシンの命令の「ステップ数」に、「空間計算量」はある計算に必要なチューリングマシンの「テープの長さ」に対応します。

決定性チューリングマシンで、$O(f(x))$で表される時間計算量の複雑性クラスを${\bf DTIME}(f(x))$で表し、同じく空間計算量の複雑性クラスを${\bf DSPACE}(f(x))$で表します。

${\bf DTIME}(f(x)),  {\bf DSPACE}(f(x))$のままでもいいのですが、代表的な複雑性クラスについては、次のような別名を付けます。ここで$p(n)$は、入力の大きさnについての多項式です。

時間複雑性については、
　　${\bf P} = {\bf DTIME}(p(n))$ ; 「多項式時間」です。
　　${\bf EXP} = {\bf DTIME}(2^{p(n)})$ ; 「指数関数的時間」です。
　　${\bf 2-EXP} = {\bf DTIME}(2^{2^{p(n)}})$ ; 「二重指数関数的時間」です。

空間複雑性については、
　　${\bf PSPACE} = {\bf DSPACE}(p(n))$ ; 「多項式空間」です。
　　${\bf EXPSPACE} = {\bf DSPACE}(2^{p(n)})$ ; 「指数関数的空間」です。
　　${\bf 2-EXPSPACE} = {\bf DSPACE}(2^{2^{p(n)}})$ ; 「二重指数関数的空間」です。

この時、 時間計算量では、${\bf P} \subset {\bf EXP}$ という関係が成り立ちます。空間計算量では、${\bf PSPACE} \subset {\bf EXPSPACE}$ という関係が成り立ちます。この辺りは、$O(p(n)) < O(2^{p(n)})$ですから、直観的にはわかりやすいかもしれません。（本当は、自明ではないのですが）

また、時間計算量と空間計算量の間では、${\bf P} \subset {\bf PSPACE} \subset {\bf EXP}$です。これは面白いですね。この図では、時間複雑性と空間複雑性が、交互に登場しています。普段、図には入れてなかったのですが、${\bf DSPACE}(log(p(n)))$で定義される複雑性クラス${\bf L}$を入れています。

ただ、この図は、大事な複雑性クラスが抜けています。そうです。${\bf P} vs. {\bf NP}$ の${\bf NP}$クラスが抜けています。次回は、${\bf P} と{\bf NP}$の問題をとりあげようと思います。