2025-11-21T16:01:16.037092

The Structure of In-Place Space-Bounded Computation

Cook, Ghentiyala, Mertz et al.

In the standard model of computing multi-output functions in logspace ($\mathsf{FL}$), we are given a read-only tape holding $x$ and a logarithmic length worktape, and must print $f(x)$ to a dedicated write-only tape. However, there has been extensive work (both in theory and in practice) on algorithms that transform $x$ into $f(x)$ in-place on a single read-write tape with limited (in our case $O(\log n)$) additional workspace. We say $f\in \mathsf{inplaceFL}$ if $f$ can be computed in this model. We initiate the study of in-place computation from a structural complexity perspective, proving upper and lower bounds on the power of $\mathsf{inplaceFL}$. We show the following: i) Unconditionally, $\mathsf{FL}\not\subseteq \mathsf{inplaceFL}$. ii) The problems of integer multiplication and evaluating $\mathsf{NC}^0_4$ circuits lie outside $\mathsf{inplaceFL}$ under cryptographic assumptions. However, evaluating $\mathsf{NC}^0_2$ circuits can be done in $\mathsf{inplaceFL}$. iii) We have $\mathsf{FL} \subseteq \mathsf{inplaceFL}^{\mathsf{STP}}.$ Consequently, proving $\mathsf{inplaceFL} \not\subseteq \mathsf{FL}$ would imply $\mathsf{SAT} \not\in \mathsf{L}$. We also consider the analogous catalytic class ($\mathsf{inplaceFCL}$), where the in-place algorithm has a large additional worktape tape that it must reset at the end of the computation. We give $\mathsf{inplaceFCL}$ algorithms for matrix multiplication and inversion over polynomial-sized finite fields. We furthermore use our results and techniques to show two novel barriers to proving $\mathsf{CL} \subseteq \mathsf{P}$. First, we show that any proof of $\mathsf{CL}\subseteq \mathsf{P}$ must be non-relativizing, by giving an oracle relative to which $\mathsf{CL}^O=\mathsf{EXP}^O$. Second, we identify a search problem in $\mathsf{searchCL}$ but not known to be in $\mathsf{P}$.

academic

インプレース空間有界計算の構造

基本情報

論文ID: 2510.12005
タイトル: The Structure of In-Place Space-Bounded Computation
著者: James Cook, Surendra Ghentiyala, Ian Mertz, Edward Pyne, Nathan Sheffield
分類: cs.CC（計算複雑性）、cs.DS（データ構造とアルゴリズム）
発表日: 2025年10月13日（arXiv プレプリント）
論文リンク: https://arxiv.org/abs/2510.12005

要約

本論文は、構造複雑性理論の観点からインプレース（in-place）空間有界計算を初めて体系的に研究する。標準的な対数空間関数計算モデル（FL）では、アルゴリズムは読み取り専用入力テープ、対数長の作業テープ、および書き込み専用出力テープを使用する。一方、インプレース計算モデル（inplaceFL）は、単一の読み書きテープ上で入力xを f(x) に変換することを要求し、O(log n)の追加作業空間のみを使用する。本論文は inplaceFL の上界と下界を証明し、以下を含む：(1) 無条件に FL ⊄ inplaceFL を証明；(2) 暗号学的仮定の下で、整数乗法と NC₄⁰ 回路評価は inplaceFL に属さないが、NC₂⁰ 回路評価は inplaceFL で完成可能であることを証明；(3) FL ⊆ inplaceFLS2P を証明し、inplaceFL ⊄ FL が SAT ∉ L を蕴含することを示す。本論文はまた触媒的インプレース計算（inplaceFCL）を研究し、多項式サイズ有限体上の行列乗法と逆行列計算のアルゴリズムを提供し、CL ⊆ P を証明するための2つの新しい障害を示す。

研究背景と動機

問題背景

従来の空間有界計算モデルはトランスデューサーを使用する：入力は読み取り専用テープ上にあり、出力は書き込み専用テープに書き込まれ、有界長の読み書き作業テープを借用する。これは理論的設定では合理的だが、実際の応用では、別の自然な定義は「読み書きテープ上の入力が与えられた場合、入力を出力に変異させるために必要な追加の読み書き作業空間はいくらか？」である。

研究動機

実用的需要：インプレースアルゴリズムは大規模データセット処理時のメモリ最適化に重要な価値を持ち、ソート、高速フーリエ変換、計算幾何学などの分野で広く応用されている
理論的空白：インプレースアルゴリズムは応用で広く研究されているが、複雑性理論の観点からの体系的構造分析が不足している
触媒計算との関連：インプレース計算は触媒計算における「圧縮またはランダム化」フレームワークの中核成分であり、その能力の理解は触媒空間理論に重要な意義を持つ

既存の限界

既存のインプレースアルゴリズム研究は主に特定の問題に焦点を当てており、一般的な複雑性クラスの特性化が不足している
インプレース計算と標準空間クラス間の関係の理解が不十分である
触媒計算における圧縮アルゴリズムはインプレース実装を必要とするが、体系的な理論ツールが不足している

核心的貢献

インプレース空間複雑性クラスの初めての体系的定義と研究：inplaceFL と inplaceFCL を形式的に定義し、インプレース計算の理論フレームワークを確立
分離結果の証明：
- 無条件に FL ⊄ inplaceFL を証明（命題1.1）
- 暗号学的仮定の下で unifNC₄⁰ ⊄ inplaceFCL を証明（定理1.3）
インプレースアルゴリズム能力の実証：
- unifNC₂⁰ ⊆ inplaceFL を証明（定理1.6）
- 有限体上の行列乗法と逆行列計算のインプレースアルゴリズムを提供（定理1.7-1.9）
複雑性理論との関連性の確立：
- FL ⊆ inplaceFLS2P を証明し、インプレース計算と多項式階層の関連性を確立（定理1.4）
- 予言機を構成して CLᴼ = EXPᴼ を実現し、CL ⊆ P の証明には非相対化証明が必要であることを証明（定理1.10）
CL に属するが P に属するかどうか不明な具体的問題の特定：C-LossyCode ∈ searchCL を証明（定理1.11）

方法論の詳細

タスク定義

インプレース計算モデル

定義3.4 (inplaceFSPACE)：関数族 {fₙ : {0,1}ⁿ → {0,1}^m(n)}ₙ∈ℕ は inplaceFSPACEs に属する。これは、チューリング機械 M が存在し、設定 x ∘ 0^max{0,m(n)-n} ∘ 0ˢ 上で実行されるとき、停止時にテープが設定 fₙ(x) ∘ 1^max{0,n-m(n)} ∘ 1ˢ にあることを意味する。