LIPIcs.FSTTCS.2019.16.pdf
- Filesize: 0.52 MB
- 13 pages
Document
Unambiguous Catalytic Computation
Authors
Rahul Jain 
,
-
Part of:
Volume:
39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-12-04
File
Document Identifiers
Author Details
Acknowledgements
The fourth author would like to thank Michal Koucký for valuable discussions and for suggesting key ideas which led to the proof of the main result in this paper. The first and third author would like to thank Ministry of Electronics and IT, India for supporting this research through the Visvesvaraya PhD. The authors would also like to thank the anonymous reviewers for their valuable comments which helped in improving the presentation of this paper and suggesting an alternative proof of CNL = coCNL as a corollary of our result.
Cite AsGet BibTex
Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari. Unambiguous Catalytic Computation. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.16
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.16
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.
Subject Classification
ACM Subject Classification
- Mathematics of computing
Keywords
- Catalytic computation
- Logspace
- Reinhardt-Allender
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Eric Allender, Klaus Reinhardt, and Shiyu Zhou. Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds. J. Comput. Syst. Sci., 59(2):164-181, October 1999. URL: https://doi.org/10.1006/jcss.1999.1646.
- Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, and Florian Speelman. Computing with a Full Memory: Catalytic Space. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 857-866, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2591796.2591874.
- Harry Buhrman, Michal Koucký, Bruno Loff, and Florian Speelman. Catalytic Space: Non-determinism and Hierarchy. Theory of Computing Systems, 62(1):116-135, January 2018. URL: https://doi.org/10.1007/s00224-017-9784-7.
-
Neil Immerman. Nondeterministic Space is Closed Under Complement. SIAM Journal on Computing, 17:935-938, 1988.
- Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 220-229, New York, NY, USA, 1997. ACM. URL: https://doi.org/10.1145/258533.258590.
- Adam R. Klivans and Dieter van Melkebeek. Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. SIAM J. Comput., 31(5):1501-1526, May 2002. URL: https://doi.org/10.1137/S0097539700389652.
- Klaus Reinhardt and Eric Allender. Making Nondeterminism Unambiguous. SIAM J. Comput., 29(4):1118-1131, February 2000. URL: https://doi.org/10.1137/S0097539798339041.
-
Robert Szelepcsényi. The Method of Forced Enumeration for Nondeterministic Automata. Acta Informatica, 26:279-284, 1988.