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

The Structure of In-Place Space-Bounded Computation

基本信息

论文ID: 2510.12005
标题: The Structure of In-Place Space-Bounded Computation
作者: James Cook, Surendra Ghentiyala, Ian Mertz, Edward Pyne, Nathan Sheffield
分类: cs.CC (Computational Complexity), cs.DS (Data Structures and Algorithms)
发表时间: 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的两个新障碍。

研究背景与动机

问题背景

传统的空间有界计算模型使用转换器(transducer)：输入在只读带上，输出写到只写带上，借助有界长度的读写工作带。这在理论设置中是合理的，但在实际应用中，另一种自然的定义是"给定读写带上的输入，需要多少额外的读写工作空间来将输入变异为输出？"

研究动机

实际需求：原地算法在处理大数据集时具有重要的内存优化价值，在排序、快速傅里叶变换、计算几何等领域有广泛应用
理论空白：尽管原地算法在应用中被广泛研究，但缺乏从复杂性理论角度的系统性结构分析
催化计算联系：原地计算是催化计算中"压缩或随机"框架的核心组件，理解其能力对催化空间理论具有重要意义

现有局限性

现有原地算法研究主要针对特定问题，缺乏一般性的复杂性类刻画
对原地计算与标准空间类之间关系的理解不充分
催化计算中的压缩算法需要原地实现，但缺乏系统的理论工具

核心贡献

首次系统定义并研究原地空间复杂性类：形式化定义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ˢ。