Unconditional Separation between LL and CLL

Abstract

Catalytic computation involves the study of Turing machines that are provided an additional catalytic tape (with arbitrary content) that the machine may use while ensuring that the tape contents are restored at the end of the computation. Although it is known that catalytic log-space machines are at least as powerful as non-deterministic log-space (and more), we do not have unconditional asymptotic separations. In this work, we prove an unconditional separation between a deterministic space complexity class and its catalytic counterpart. More precisely, at the doubly logarithmic scale, we show that catalytic Turing machines can provably compute more languages than standard deterministic doubly-logarithmic space machines. The separation is witnessed by the unary language $POW2=\{1^n:n\text{ is a power of two}\}$. We construct a catalytic Turing machine that uses $O(\log \log n)$ bits of space and $O(\log n)$ bits of catalytic tape to decide $POW2$, whereas any standard deterministic Turing machine requires $\Omega (\log n)$ space to decide it.

arXiv comment11 pages. v2: fixed an error in the upper bound concerning the endmarkers of the catalytic tape; thanks to András Salamon for pointing it out