Veröffentlichung

Titel:

Randomized and Symmetric Catalytic Computation

AutorInnen:

Samir Datta
Chetan Gupta
Rahul Jain
Vimal Raj Sharma
Raghunath Tewari

Kategorie:

Konferenzbandbeiträge

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

Abstract:

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.

Download:

Springer

BibTeX-Eintrag:

@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 = {https://doi.org/10.1007/978-3-030-50026-9\_15}, doi = {10.1007/978-3-030-50026-9\_15}, timestamp = {Thu, 06 Aug 2020 21:49:44 +0200}, biburl = {https://dblp.org/rec/conf/csr/Datta00ST20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }