{"ID":2856622,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.12005","arxiv_id":"2510.12005","title":"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}\\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}$.","short_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 $...","url_abs":"https://arxiv.org/abs/2510.12005","url_pdf":"https://arxiv.org/pdf/2510.12005v1","authors":"[\"James Cook\",\"Surendra Ghentiyala\",\"Ian Mertz\",\"Edward Pyne\",\"Nathan S. Sheffield\"]","published":"2025-10-13T22:58:00Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}