Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.24
URN: urn:nbn:de:0030-drops-57258
URL: https://drops.dagstuhl.de/opus/volltexte/2016/5725/
Buhrman, Harry ; Koucký, Michal ; Loff, Bruno ; Speelman, Florian
Catalytic Space: Non-determinism and Hierarchy
| pdf-format: |
|
Abstract
Catalytic computation, defined by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), is a space-bounded computation where in addition to our working memory we have an exponentially larger auxiliary memory which is full; the auxiliary memory may be used throughout the computation, but it must be restored to its initial content by the end of the computation.Motivated by the surprising power of this model, we set out to study the non-deterministic version of catalytic computation. We establish that non-deterministic catalytic log-space is contained in ZPP, which is the same bound known for its deterministic counterpart, and we prove that non-deterministic catalytic space is closed under complement (under a standard derandomization assumption). Furthermore, we establish hierarchy theorems for non-deterministic and deterministic catalytic computation.
BibTeX - Entry
@InProceedings{buhrman_et_al:LIPIcs:2016:5725,
author = {Harry Buhrman and Michal Kouck{\'y} and Bruno Loff and Florian Speelman},
title = {{Catalytic Space: Non-determinism and Hierarchy}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {24:1--24:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-001-9},
ISSN = {1868-8969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5725},
URN = {urn:nbn:de:0030-drops-57258},
doi = {10.4230/LIPIcs.STACS.2016.24},
annote = {Keywords: catalytic computation, Immerman–Szelepcs{\'e}nyi theorem, space hierarchy}
}
| Keywords: | catalytic computation, Immerman–Szelepcsényi theorem, space hierarchy | |
| Seminar: | 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 16.02.2016 |
