Catalytic computation asks: how much does access to a full but reusable tape amplify our computational power? In this talk, we explore this question in the context of graph algorithms and logspace complexity.
We present three results: NL ⊆ CL, showing that nondeterministic logspace computations can be simulated catalytically; BPL ⊆ CL, showing the same for randomized logspace; and the collapse CBPL = CNL = CL, revealing that in the catalytic regime, nondeterminism and randomness likely afford no additional power over determinism — a striking contrast to the standard logspace world where such separations remain wide open.
We also discuss some key design principles that underpin catalytic algorithms.
