Collapsing Catalytic Classes

Michal Koucký, Ian Mertz · 2025

Read Collapsing Catalytic Classes by Michal Koucký, Ian Mertz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-08444.txt.

Introduction

Michal Koucky and co-authors settle open questions in a computing model called catalytic space in a 2025 paper. A catalytic machine has a small work tape plus a large tape that starts full. The machine may use the large tape but must restore its contents exactly.

Earlier work showed this setup holds surprising power, and variants added randomness or guessing. Many basic questions stayed open, such as catalytic versions of classic space theorems. A recent result removed randomness only in narrow settings. The new paper reduces catalytic space with extra resources to the matching plain space classes. That reduction is optimal and closes nearly all questions about the randomized and guessing variants.

Catalog record

CREATORMichal Koucký, Ian Mertz
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-08444

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Collapsing Catalytic Classes Thanks: Supported by the NSF GRFP. Michal Koucký, Ian Mertz Abstract A catalytic machine is a space-bounded Turing machine with additional access to a second, much larger work tape, with the caveat that this tape is full, and its contents must be preserved by the computation. Catalytic machines were defined by Buhrman et al. (STOC 2014), who, alongside many follow-up works, exhibited the power of catalytic space ( CSPACE ) and in particular catalytic logspace machines ( CL ) beyond that of traditional space-bounded machines. Several variants of CL have been proposed, including non-deterministic and co-non-deterministic catalytic computation by Buhrman et al. (STACS 2016) and randomized catalytic computation by Datta et. al. (CSR 2020). These and other works proposed several questions, such as catalytic analogues of the theorems of Savitch and Immerman and Szelepcsényi. Catalytic computation was recently derandomized by Cook et al. (STOC 2025), but only in certain parameter regimes. We settle almost all questions regarding non-deterministic and randomized catalytic computation, by giving an optimal reduction from catalytic space with additional resources to the corresponding non-catalytic space classes. With regards to non-determinism, our main result is that CL = CNL {\text{CL}}={\text{CNL}} and with regards to randomness, we show CL = CPrL {\text{CL}}={\text{CPrL}} where CPrL denotes randomized catalytic logspace where the accepting probability can be arbitrarily close to 1 / 2 1/2 . We also have a number of near-optimal partial results for non-deterministic and randomized catalytic computation with less catalytic space. In particular, we show catalytic versions of Savitch’s theorem, Immerman-Szelepscényi, and the derandomization results of Nisan and Saks and Zhou, all of which are unconditional and hold for all parameter settings. Our results build on the compress-or-compute framework of Cook et al. (STOC 2025). Despite proving broader and stronger results, our framework is simpler and more modular. 1 Introduction In this paper we study space-bounded classes with access to additional resources. The three resources we study are non-determinism , randomness , and, most central to this work, catalytic space . The first two models, i.e. non-deterministic and randomized space, have long yet unresolved histories going back to the earliest days of theoretical computer science. The first major result, due to Savitch in 1970 [ Sav70 ] , states that determinism can simulate non-determinism with only a quadratic space overhead, i.e. {\text{NSPACE}}[s]\subseteq{\text{SPACE}}[s^{2}] . Much later, Nisan [ Nis92 ] and Saks and Zhou [ SZ99 ] proved that bounded-error randomness can similarly be simulated with an even smaller blowup, showing {\text{BPSPACE}}[s]\subseteq{\text{SPACE}}[s^{3/2}] . In between, Borodin, Cook, and Pippenger [ BCP83 ] derandomized unbounded-error randomized computation with a quadratic space blowup, i.e. {\text{PrSPACE}}[s]\subseteq{\text{SPACE}}[s^{2}] . While derandomization in the bounded-error case continues to see vigorous work—the exponent has since been further improved by Hoza [ Hoz21 ] by a o(1) factor—Savitch’s Theorem remains the best known simulation for non-determinism to date. Subsequent results by Immerman and Szelepscényi [ Imm88 , Sze88 ] and Reinhardt and Allender [ RA00 ] show progress from a different angle, namely by showing that NL is closed under complement ( {\text{NL}}={\text{coNL}} ), and NL can be made unambiguous ( {\text{NL}}={\text{UL}} ) assuming strong circuit lower bounds, respectively. Meanwhile, while [ BCP83 ] shows that {\text{PrL}}={\text{PrSPACE}}[O(\log n)]\subseteq{\text{TC${}^{1}$}} , a slightly stronger containment than {\text{L}}^{2} , there have been no other improvements on unbounded-error derandomization. 1.1 Catalytic Computation We now turn our attention to our third resource. The catalytic space model, introduced by Buhrman, Cleve, Koucký, Loff, and Speelman [ BCK+14 ] , studies the question of whether full space can be useful to computation. In {\text{CSPACE}}[s,c] we consider a typical {\text{SPACE}}[s] machine augmented with a second work tape, called the catalytic tape , which has length c . We think of c to be much larger than s , often exponentially larger; however, this tape is initialized to some arbitrary string \tau , and at the end of the computation our machine must reset the catalytic tape to the starting \tau . Despite this restriction, [ BCK+14 ] show that such machines are unexpectedly powerful. Focusing on the class called catalytic logspace ( {\text{CL}}:={\text{CSPACE}}[O(\log n),\poly(n)] ), they show that the catalytic tape is at least as powerful as randomization and non-determinism ( BPL and NL , respectively), and contains problems (e.g. determinant) which are thought to be in neither. Catalytic computation appeared in the context of composition for space-bounded functions, where it was unknown whether computing multiple instances of a function causes the space complexity to scale up linearly in tandem. Such techniques and insights were crucially used in the recent result of Cook and Mertz [ CM21 , CM22 , CM24 ] on the tree evaluation problem, which was later used in a breakthrough by Williams [ Wil25 ] showing {\text{TIME}}[t] can be simulated in only \sqrt{t\log t} space. 1.2 Non-Deterministic and Randomized Catalytic Computation In light of the surprising power of catalytic space, follow-up works have proposed several variants of the base model, such as non-deterministic catalytic computation [ BKLS18 , GJST19 , MS24 ] , randomized catalytic computation [ DGJ+20 , CLMP25 ] , non-uniform catalytic computation [ GKM15 , Pot17 , RZ21 , CM22 ] , and error-prone catalytic computation [ GJST24 , FMST25 ] , to name a few (see surveys of Koucký [ Kou16 ] and Mertz [ Mer23 ] for an overview). Non-deterministic catalytic space was introduced by Buhrman et al. [ BKLS18 ] , who showed that, assuming pseudorandom generators, catalytic non-deterministic logspace ( CNL ) is also closed under complement ( {\text{CNL}}={\text{coCNL}} ). Later work of [ GJST19 ] extended this by showing, again assuming pseudorandom generators, that CNL can also be made unambiguous ( {\text{CNL}}={\text{CUL}} ). The question of proving such statements unambiguously, or of obtaining a catalytic analogue of Savitch’s Theorem, was put forth several times as an open question [ BKLS18 , GJST19 , Kou16 , Mer23 , CLMP25 ] . Randomized catalytic space was introduced by Datta et al. [ DGJ+20 ] , where they showed that catalytic randomized logspace ( CBPL ) equals CL under similar pseudorandomness assumptions. This was recently shown unconditionally by Cook et al. [ CLMP25 ] ; however, their result only holds for {\text{CSPACE}}[s,c] when c=2^{\Theta(s)} , while the general case is of interest in other settings [ BDS22 , Pyn24 , FMST25 ] . Thus far there has been no study of unbounded error randomness in catalytic computation ( CPrL ). 1 1 1 Terminology for unbounded error randomized classes varies between using Pr and simply P, but as we will be introducing e.g. CPrSPACE the latter creates too many collisions between “probabilistic” and “polynomial”. 1.3 Our Results We settle essentially every question regarding non-deterministic and randomized catalytic computation. Our most striking result is that, with access to a large pre-filled hard drive, neither non-determinism nor unbounded-error randomness gives any additional power: Theorem 1 . {\text{CL}}={\text{CNL}}. Theorem 2 . {\text{CL}}={\text{CPrL}}. From these results we conclude in the context of space-bounded computation, catalytic space acts as one resource to rule them all. We note that before our result there were no non-trivial connections between deterministic catalytic computation and either non-deterministic or unbounded-error randomized catalytic computation, even under assumptions. We also have a number of results for

Read the complete text