Unambiguous, Randomized, and Symmetric Catalytic Computation

A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape, which is initially filled with arbitrary content; the machine can read or write on the auxiliary tape during the computation, but it is constrained to halt with the same content in the auxiliary tape as it initially had. This paper, studies the power of some natural variants of catalytic Turing machines with O (log n )-size work tape and a polynomial-size auxiliary tape. We first define the notion of unambiguous catalytic Turing machines and prove that under a standard derandomization assumption, the class of problems solved by unambiguous catalytic Turing machines is the same as the class of problems solved by nondeterministic catalytic Turing machines. We then introduce the notion of randomized catalytic Turing machines and show that the resulting complexity class CBPL is contained in the class ZPP. We also explore the notion of symmetricity in the context of catalytic computation and prove that, under the same assumption as before, randomized catalytic Turing machines, symmetric catalytic Turing machines, and deterministic catalytic Turing machines that run in polynomial time are equally powerful.