The Structure of Catalytic Space: Capturing Randomness and Time via Compression

In the catalytic logspace (CL) model of (Buhrman et. al. STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. This model is of interest from a complexitytheoretic perspective as it gains surprising power over traditional space. However, many fundamental structural questions remain open.

We substantially advance the understanding of the structure of CL, addressing several questions raised in prior work. Our main results are as follows.

(1) We unconditionally derandomize catalytic logspace: CBPL = CL. (2) We show time and catalytic space bounds can be achieved separately if and only if they can be achieved simultaneously: any problem in CL ∩ P can be solved in polynomial timebounded CL. (3) We characterize deterministic catalytic space by the intersection of randomness and time: CL is equivalent to polytimebounded, zero-error randomized CL.

Our results center around the compress-or-random framework. For the second result, we introduce a simple yet novel compress-orcompute algorithm which, for any catalytic tape, either compresses the tape or quickly and successfully computes the function at hand. For our first result, we further introduce a compress-or-compressor-random algorithm that combines runtime compression with a second compress-or-random algorithm, building on recent work on distinguish-to-predict transformations and pseudorandom generators with small-space deterministic reconstruction.