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

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

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

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

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

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

決定性チューリングマシンで、\(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}\)の問題をとりあげようと思います。