License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.16
URN: urn:nbn:de:0030-drops-115782
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11578/
Go to the corresponding LIPIcs Volume Portal

Gupta, Chetan ; Jain, Rahul ; Sharma, Vimal Raj ; Tewari, Raghunath

Unambiguous Catalytic Computation

pdf-format:
LIPIcs-FSTTCS-2019-16.pdf (0.5 MB)

Abstract

The 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.

BibTeX - Entry

@InProceedings{gupta_et_al:LIPIcs:2019:11578,
  author =	{Chetan Gupta and Rahul Jain and Vimal Raj Sharma and Raghunath Tewari},
  title =	{{Unambiguous Catalytic Computation}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11578},
  URN =		{urn:nbn:de:0030-drops-115782},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.16},
  annote =	{Keywords: Catalytic computation, Logspace, Reinhardt-Allender}
}

Keywords: Catalytic computation, Logspace, Reinhardt-Allender
Collection: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 04.12.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI