ECCC-Report TR19-095https://eccc.weizmann.ac.il/report/2019/095Comments and Revisions published for TR19-095en-usSun, 21 Jul 2019 14:21:02 +0300
Paper TR19-095
| Unambiguous Catalytic Computation |
Chetan Gupta,
Rahul Jain,
Vimal Raj Sharma,
Raghunath Tewari
https://eccc.weizmann.ac.il/report/2019/095The catalytic Turing machine is a model of computation defined by Buhrman, Cleve,
Kouck, Loff, and Speelman (STOC 2014). Compared to the classical space-bounded Turing
machine, this model has an extra space which is filled with arbitrary content in addition
to the clean space. In such a model we study if this additional filled space can be used to
increase the power of computation or not, with the condition that the initial content of this
extra filled space must be restored at the end of the computation.
In this paper, we define the notion of unambiguous catalytic Turing machine and prove
that under a standard derandomization assumption, the class of problems solved by an
unambiguous catalytic Turing machine is same as the class of problems solved by a general
nondeterministic catalytic Turing machine in the logspace setting.Sun, 21 Jul 2019 14:21:02 +0300https://eccc.weizmann.ac.il/report/2019/095