Class Description

CL: Catalytic Logspace

The class CSPACE with work space ${\displaystyle O(\log n)}$ and catalytic space ${\displaystyle n^{O(1)}}$.

Contains TC¹ and is contained in ZPP [BCKLS14].

Defined in [BCKLS14].

Linked From

CSPACE: Catalytic space

A catalytic Turing machine with space s and catalytic space c is defined as an ordinary Turing machine with a worktape of size s plus an additional worktape of size c, called the catalytic tape, with the restriction that the catalytic tape starts in some configuration ${\displaystyle \tau \in \{0,1\}^{c}}$ and with the restriction that every computation path of the machine ends with the catalytic tape in the same configuration ${\displaystyle \tau }$.

CSPACE(s,c) is the class of decision problems recognizable by catalytic Turing machines with space s and catalytic space c. In most works c is exponential in s, as this is the largest amount of catalytic space which can still be addressed into by the worktape.

Defined in [BCKLS14]. Main variant studied is CL.

Can also be defined non-uniformly by way of catalytic branching programs [GKM15], but the relationship to traditional advice classes (i.e. CSPACE/poly) is unknown. In this setting the relationship between s and c is less constrained, often with s being constant.

More about...