Class Description

CL: Catalytic Logspace

The class CSPACE with work space and catalytic space .

Contains TC1 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 and with the restriction that every computation path of the machine ends with the catalytic tape in the same configuration .

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...