Randomized and Symmetric Catalytic Computation
Samir Datta
Chetan Gupta
Rahul Jain
Vimal Raj Sharma
Raghunath Tewari
erschienen in:
Computer Science - Theory and Applications - Proceedings of the 15th International Computer Science Symposium in Russia, {CSR} 2020, Lecture Notes in Computer Science, Vol. 12159, pp. 211-223

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 𝑂(log 𝑛)-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 is contained in the class 𝖹𝖯𝖯. 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.

@inproceedings{DBLP:conf/csr/Datta00ST20, author = {Samir Datta and Chetan Gupta and Rahul Jain and Vimal Raj Sharma and Raghunath Tewari}, editor = {Henning Fernau}, title = {Randomized and Symmetric Catalytic Computation}, booktitle = {Computer Science - Theory and Applications - 15th International Computer Science Symposium in Russia, {CSR} 2020, Yekaterinburg, Russia, June 29 - July 3, 2020, Proceedings}, series = {Lecture Notes in Computer Science}, volume = {12159}, pages = {211--223}, publisher = {Springer}, year = {2020}, url = {\_15}, doi = {10.1007/978-3-030-50026-9\_15}, timestamp = {Thu, 06 Aug 2020 21:49:44 +0200}, biburl = {}, bibsource = {dblp computer science bibliography,} }
Christoph Doppelbauer | 20.10.2021