1 空間計算量の基本
1.1 定義と直感
空間計算量とは、入力を受けて計算が進行する間に、計算機が必要とする記憶資源（メモリ量）を、入力サイズに関する関数として評価する枠組みである。時間計算量が「いつ終わるか（どれだけ実行ステップを要するか）」を主題にするのに対し、空間計算量は「実行中にどれだけ情報を保持する必要があるか」を焦点に置く。ここでの“記憶”は、現在の状態や作業用データ、探索履歴など、計算を成立させるために不可欠な保持分を指す。
直観的には、問題の解が一意に決まるだけでなく、探索や検証の過程で参照する情報がどれほど多くなるかが空間を決める。例えば、深い探索を行うとしても、再利用できる情報が多ければメモリを節約できる。一方、途中結果を広く保持し続ける必要がある設計だと、空間消費が増えやすい。
1.2 空間計算量の表し方
1.2.1 入力サイズに対する表現
入力サイズを \(n\) とし、計算機が使用する作業領域の量を \(s(n)\) と表すのが基本形である。典型的には「入力全体に対し、計算中に必要となる作業セル数が \(O(s(n))\) で抑えられる」などの形で記述する。
また、問題によって必要量が異なるため、定義では“最悪時”を用いることが多い。すなわち、長さ \(n\) の入力のうち最も記憶を要する場合の消費量を基準にする。これにより、計算クラスの比較が安定し、異なるモデル間の議論とも接続しやすくなる。
1.2.2 記憶量の測定単位（セル数など）
測定単位は計算モデルに依存する。代表例はテープ上のセル数で、読み書き可能な作業領域を何セル分確保するかを数える。別のモデルでは、メモリの“ワード数”や“バイト相当”に対応する量で表すこともある。
ただし測定単位が変わると定数因子や拡大の仕方が変わるため、分類ではしばしば漸近的な一致（多項式同士の比較など）を重視する。たとえば、入力長に対して線形に増える資源を測っているのか、対数的に増えるのか、という成長率が結論の中心になる。
1.3 計算モデルとの関係
1.3.1 チューリング機械における定義
チューリング機械の枠組みでは、作業用テープ（あるいは複数テープのうち作業に使う領域）の利用範囲が空間計算量の核になる。機械が実行の途中で実際に触れるテープ領域の広がりを数え、その上限を空間計算量として定める。
重要なのは「計算がどれだけ長く続くか」ではなく、「計算中に、どの程度広い記憶領域を必要としているか」である。探索アルゴリズムの実装では、スタックとしての経路情報を保持するか、到達したノード集合を保持するかといった実装差が空間の違いとして現れる。
1.3.2 他モデルへの対応
ランダムアクセス計算機など、別の計算モデルでは内部表現やアクセス方法が異なるため、同じ直観でも測定値がずれる可能性がある。そのため一般には「計算モデルが持つ基本操作の表現能力」を揃え、空間計算量の定義を再解釈する。
多くの場合、モデル変更に対して空間計算量は大きくは変わらず、定数因子や低次の項の差に吸収されることが望まれる。これにより、クラスの同定や包含関係の議論が、モデルに依存しすぎない形で進む。
2 計算クラスとしての空間計算量
2.1 決定性空間クラス
2.1.1 L（対数空間）
L は決定性計算機で、必要とする作業領域が入力長の対数オーダーで抑えられる問題クラスとして扱われる。対数空間では、保持できる情報量が \(O(\log n)\) ビット程度に限られるため、巨大な補助記憶に依存する解法は採りにくい。その制約の下で、入力の位置を表すインデックスや、探索のための簡潔な状態情報を工夫することが中心になる。
幅広い定式化と見方ができる点も重要である。例えば、特定の計算やグラフ操作における“簡潔な記録”として捉える道筋がある。さらに、関数の評価や行列に関する到達可能性のように、局所的な再計算を許して全体を保持しない設計が現れやすい。
2.1.1.1 幅広い定式化と代表的性質
L は対数空間での決定可能性を表し、同クラス内の問題は計算資源の性質により相互に還元できる場合がある。一般に、空間制約が厳しいほど「保持する情報が少ない」代わりに「必要なときに再計算する」方向へ設計が寄りやすい。その結果として、計算の可逆性や補助構造の圧縮といった考え方が関連しやすくなる。
また、L と関係の深い構造として有向グラフの到達可能性が挙げられることが多い。特定の表現形式のもとで、経路そのものを保存せずに到達性を判定する工夫が成立するためである。こうした例は、空間が少ない状況でも決定を行える領域が存在することを示す。
2.1.2 多項式空間（例：Pと対比）
多項式空間は一般に PSPACE というクラス名で知られる議論に接続し、ここでは比較の観点として、多項式時間の P と対比されることが多い。P は「時間が多項式で抑えられる」問題群であり、多項式空間は「メモリが多項式で抑えられる」問題群である。
時間と空間はしばしば連動するが、片方が多項式でも他方が必ずしも同程度に制限されるとは限らない。時間制約が緩くても空間が強く制約されると、アルゴリズムの選択肢が変わる。逆に、空間の上限が高いと時間が指数的に伸びても許容される可能性が出る。この差を理解することが、空間計算量を導入する動機になる。
2.2 非決定性空間クラス
2.2.1 NL（非決定性対数空間）
NL は非決定性計算機における対数空間クラスとして位置付けられる。非決定性では分岐を許すため、「どの分岐経路が成功するか」を探索する必要が生じるが、保存できる情報が対数空間に制限される点は同じである。したがって、分岐探索の管理を、長い履歴保存なしに行えるかが鍵になる。
典型的には、グラフ上の到達可能性を非決定的に“推測して検証する”視点で捉えられる。推測するのは経路の選択に関わる部分情報で、検証は入力に基づく局所条件で済ませる構成が取りやすい。その結果、経路全体をメモリに蓄えない形で到達性に関する判断が可能となる。
2.2.2 非決定性と包含関係
非決定性と決定性の関係は、空間計算量の領域で重要なテーマになる。特に、非決定性空間が一定の条件の下で決定性空間へ変換できるような包含関係が成り立つことがある。ここでの核心は「分岐の存在が、必要な記憶の増大を必ずしも招かない場合がある」という点にある。
その一方で、一般に“時間”より“空間”のほうが非決定性の扱いで構造的な性質が出やすいとされる。したがって、空間クラスの包含関係は、決定性・非決定性の違いを理解する上で、比較的整理された像を提供する。
2.3 一般の空間クラス（PSPACEなど）
2.3.1 空間クラスの階層構造
PSPACE は、多項式空間で決定可能な問題からなる広いクラスとして捉えられる。空間制約の関数が増えるにつれて、到達できる問題集合は拡大する。これにより空間計算量は階層として理解でき、例えば「対数空間 ⊂ 多項式空間 ⊂ さらに大きい空間」のような並びが議論の土台になる。
また、階層の各段は、アルゴリズム設計で使えるメモリの増加に対応している。保持できる中間結果が増えると、探索のやり方や検証の実行形態が変わるため、含める問題の性質も変化する。
2.3.2 完全性と基準の考え方
空間クラスにおいても、典型的には“完全性”という概念が用いられる。ある問題がクラス内で最も難しい（基準的である）ことを示す役割で、還元（変換）により他の問題がその問題へ落とせる状態を意味する。
完全性を語る際、還元の種類（どれくらいの計算資源で変換するか）を明確にする必要がある。空間計算量では、変換に使う追加メモリが許容量を超えないよう制御することが重要になる。基準問題は、空間制約のもとでどの操作が本質的に難しさを生むかを示す指標として機能する。
3 空間計算量の変換・等価性
3.1 計算モデルの変更による影響
3.1.1 テープ枚数やヘッド操作の違い
同じチューリング機械でも、テープの枚数や読み書きヘッドの振る舞いが異なる場合がある。これらの変更は、実装上の操作回数だけでなく、必要な作業領域の見積りにも影響しうる。
ただし多くの理論では、テープ枚数の固定や、ヘッド操作の制約が違っても、空間計算量は同じ成長率で表せるように整合させる。例えば、複数テープの機能を単一テープでエミュレートすることは可能であり、その際の空間増加が許容範囲に収まる設計が求められる。
3.1.2 定数因子と多項式因子の扱い
空間計算量の比較では、厳密な係数よりも増加率が論点になることが多い。そこで、定数因子の差や、操作の表現に伴う低次の増加は、クラス判定に影響しない形で吸収するのが一般的である。
一方で、空間関数が対数から多項式へといった異なる成長帯を跨ぐと、結論は大きく変わる。したがって、変換によって係数が増えるのではなく、次数やオーダーが変わっていないことを確認する必要がある。
3.2 時間と空間の関係
3.2.1 包含関係の基本像
時間と空間は単純な包含関係で一意に結びつかないが、一般に「時間が増えると空間の必要性が下がる」といった単純反比例が常に成立するわけではない。空間制約と時間制約は、それぞれ異なるボトルネックを反映するためである。
とはいえ、ある形の変換（再計算や探索の設計）を行うことで、両者が一方から制御される状況も現れる。代表的には、空間を抑えつつ時間を増やしても正しさを維持できるような再探索方針が利用される。この方向性は“メモリが少ないので時間で補う”という直観と一致する。
3.2.2 トレードオフの直観
空間節約は、しばしば中間情報を保持せず、その都度参照元から再構成する発想につながる。再構成に必要な手続きが増えれば時間は伸びるため、トレードオフが生じる。
他方、時間節約を狙って大量の中間結果を保存すると空間が膨らみやすい。したがってアルゴリズム設計では、保持すべき情報の粒度を調整し、必要な計算の再実行回数を見積もる作業が重要になる。結果として、同じ問題でも実装方針により、時間・空間のバランスが変化する。
3.3 具体的変換手法
3.3.1 入力の保持と再読込戦略
入力そのものは有限の長さであり、通常は外部記憶に保持されたものとしてモデル化されることが多い。そのため、空間節約では入力を“メモリに展開せず、必要なときに参照する”設計が役立つ。
具体的には、インデックスを保持して該当位置を読み直すことで、入力全体を複製する代わりに作業領域を抑える。これにより、保持すべき情報は位置情報などの簡潔なデータに限られるため、対数近傍のメモリで運用できる場面が増える。
3.3.2 中間状態の圧縮
計算途中の情報をそのまま保持するのではなく、同等な推論を可能にする形へ圧縮することで空間が削減される。圧縮は、冗長な履歴を削り、必要十分な指標だけを残す方向で行われる。
圧縮の設計には、(1) 再利用可能な性質の特定、(2) 保持する表現の設計、(3) 圧縮された情報から必要な判定を再構成できることの確認、が含まれる。例として、到達可能性のような問題では、経路全体ではなく、探索の制御に必要な状態のみを持つことで空間の削減が可能になる。
4 空間制約下での典型問題
4.1 グラフ問題と空間計算量
4.1.1 到達可能性と探索の考え方
グラフにおける到達可能性（ある頂点から別の頂点へ経路が存在するか）は、空間制約と相性がよい代表的題材である。経路をそのまま保存すると空間が増えやすいが、経路の一部を逐次的に扱い、必要に応じて探索を進めることでメモリを節約できる。
探索の設計では、幅を広げる戦略（多くの候補を同時に保持する）ほど空間を要しやすい。一方、深さ方向の追跡や再探索を取り入れると、保持量を減らして時間を増やす形の調整が行える。こうした調整が、空間クラスの境界を理解する助けになる。
4.1.2 幅優先・深さ優先とメモリ消費
幅優先探索（BFS）は、同じ距離の頂点群を順に扱うため、未処理の集合を保持しがちである。これは特に大規模なグラフで空間消費を増やしやすい。
深さ優先探索（DFS）は、現在の経路に関する情報を中心に進めるため、スタック的にメモリを使う設計になりやすい。実装では、訪問済み集合の保持の有無が重要な分岐になる。訪問済みを完全に保持すると空間は増えやすく、保持を抑えるなら再訪や探索の繰り返しが増えて時間側に負担が移る。空間制約下では、この選択がクラス差として現れやすい。
4.2 自動化理論・論理との接点
4.2.1 オートマトンと空間資源
オートマトン理論では、計算の“状態数”や“走査方法”が計算資源の直観的対応を持つ。読み取りにおけるメモリ的制約は、計算過程で必要となる情報量として空間計算量と結びつけて捉えられる。
たとえば有限オートマトンは入力長に依存しない記憶で動作するが、空間が対数的に増える段階では、計数や位置参照が可能になる。その境目に現れる振る舞いを解析することで、空間クラスの見取り図が得られることがある。
4.2.2 論理記述の計算資源対応
論理（論理式）を用いて問題を記述すると、その記述の型や量化の深さが計算資源と対応付けられることがある。特に、空間制約を持つ計算は、特定の論理断片による記述可能性と関係する形で現れることがある。
この接点の価値は、計算問題を“記述の複雑さ”の観点から分類できる可能性にある。記述の制限により、必要な推論や探索がどの程度のメモリで実行できるかが結びつくため、空間計算量の理解が言語化される。
4.3 実装上の注意（学習・設計の観点）
4.3.1 省メモリ化の方針
省メモリ化の基本方針は、(1) 保存する情報の範囲を最小化する、(2) 必要になったら再計算で補う、(3) 入力や中間表現の形式を選び直す、の三つに整理できる。
学習段階では、まず素直な実装（完全な履歴保存や大きな表の保持）を作り、どこにメモリが集中しているかを観察する方法が効果的である。次に、同じ判定を行うのに本当に必要な情報だけを残す方向へ改造することで、空間を削る手応えが得られる。
4.3.2 ボトルネックの特定方法
ボトルネックの特定では、使用メモリが増える原因を「保持データの種類」「保持の寿命（いつまで生き残るか）」「同時に必要な量」に分けて考えると整理しやすい。例えば、配列や表を保持するならサイズが支配的になり、探索履歴を保持するならスタック深さや分岐管理が支配的になる。
また、計算途中の“ピーク”がどこで発生するかを追跡することが重要である。総操作回数ではなく、最大同時保持量に注目すると、空間計算量の見積りが現実の実装に近づく。最後に、別の設計（再探索や圧縮表現）に切り替えたとき、どの因子が改善され、どの因子が時間側へ移ったかを確認することで、設計の妥当性が評価できる。