「時間計算量」と「空間計算量」
以前、次のように書きました。 「複雑なものを理解するのには、長い時間と膨大な知識の集積が必要である」と。 それは、人間の認識の歴史について語ったものでしたが、具体的な計算の複雑さの尺度にも、この「長い時間と膨大な知識の集積」に対応する量があります。 それは、「その計算にどれぐらいの時間が必要か?」という時間の尺度と、「その計算にどのくらいのメモリー空間が必要か?」という空間の尺度です。前者を「時間計算量」、後者を「空間計算量」と言います。 チューリングマシンで言えば、「時間計算量」はある計算に必要なチューリングマシンの命令の「ステップ数」に、「空間計算量」はある計算に必要なチューリングマシンの「テープの長さ」に対応します。 決定性チューリングマシンで、\(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} \sub