Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-024 | 20th February 2020 14:49

Randomized and Symmetric Catalytic Computation


Authors: Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari
Publication: 24th February 2020 12:07
Downloads: 744


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 auxiliary tape during the computation but when it halts auxiliary tape’s initial content must be restored. In this paper, we study the power of catalytic Turing machines with O(log n)-sized clean tape and a polynomial-sized auxiliary tape.

We introduce the notion of randomized catalytic Turing machine and show that the resulting complexity class CBPL is contained in the class ZPP. We also introduce the notion of symmetricity in the context of catalytic computation and prove that, under a widely believed assumption, in the logspace setting the power of a randomized catalytic Turing machine and a symmetric catalytic Turing machine is equal to a deterministic catalytic Turing machine which runs in polynomial time.

ISSN 1433-8092 | Imprint