- Catalytic space: Non-determinism and hierarchy
- Leibniz International Proceedings in Informatics
- Article number
- Number of pages
- Document type
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
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.
- go to publisher's site
- Other links
- Link to publication in Scopus
- 33rd Symposium on Theoretical Aspects of Computer Science : STACS'16, February 17-20, Orléans, France.
Edited by Nicolas Ollinger and Heribert Vollmer.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.