The Structure of In-Place Space-Bounded Computation

Abstract

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}⊈\mathsf{inplaceFL}$. ii) The problems of integer multiplication and evaluating ${\mathsf{NC}}_4^0$ circuits lie outside $\mathsf{inplaceFL}$ under cryptographic assumptions. However, evaluating ${\mathsf{NC}}_2^0$ circuits can be done in $\mathsf{inplaceFL}$. iii) We have $\mathsf{FL}\subseteq {\mathsf{inplaceFL}}^{\mathsf{STP}}.$ Consequently, proving $\mathsf{inplaceFL}⊈\mathsf{FL}$ would imply $\mathsf{SAT}\notin \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}$.

43 pages