空間は時間で抑えられる

命題 2.4（「計算量と O 記法」§2）・ ✓公理まで証明済み

アルゴリズム $A$ が、1 回の基本演算で高々 $\kappa$ 個の記憶セルにアクセスするとする（定義 2.1 のモデルではつねに $\kappa \le 3$ と取れる）。このとき、すべての $n$ に対して

S_A(n) \le n + \kappa\, T_A(n)

が成り立つ。とくに $T_A(n) \ge n$ ならば $S_A(n) = O(T_A(n))$ である。

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 0 件、定義なども含めて 1 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

証明で明示的に参照している定理は、まだありません。