Catalytic Space: Non-determinism and Hierarchy

Buhrman, Harry; Koucký, Michal; Loff, Bruno; Speelman, Florian

doi:10.4230/LIPIcs.STACS.2016.24

File

LIPIcs.STACS.2016.24.pdf

Filesize: 0.66 MB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2016.24
URN: urn:nbn:de:0030-drops-57258

Author Details

Harry Buhrman

Michal Koucký

Bruno Loff

Florian Speelman

Cite AsGet BibTex

Harry Buhrman, Michal Koucký, Bruno Loff, and Florian Speelman. Catalytic Space: Non-determinism and Hierarchy. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.STACS.2016.24

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.

Keywords

catalytic computation
Immerman–Szelepcsényi theorem
space hierarchy

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

E. Allender, H. Buhrman, M. Koucký, D. van Melkebeek, and D. Ronneburger. Power from random strings. SIAM J. Comput., 35(6):1467-1493, June 2006. URL: http://dx.doi.org/10.1137/050628994.
S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
H. Buhrman, R. Cleve, M. Koucký, B. Loff, and F. Speelman. Computing with a full memory: Catalytic space. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC'14, pages 857-866, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2591796.2591874.
N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17(5):935-938, 1988. URL: http://dx.doi.org/10.1137/0217058.
R. Impagliazzo and A. 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: http://dx.doi.org/10.1145/258533.258590.
R. Karp and R. Lipton. Turing machines that take advice. L'Enseignement Mathématique, 28:191-209, 1982.
J. Kinne and D. van Melkebeek. Space hierarchy results for randomized and other semantic models. Computational Complexity, 19(3):423-475, 2010. URL: http://dx.doi.org/10.1007/s00037-009-0277-1.
A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing, 31(5):1501-1526, 2002. URL: http://dx.doi.org/10.1137/S0097539700389652.
R. Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26(3):279-284, 1988. URL: http://dx.doi.org/10.1007/BF00299636.
D. van Melkebeek and K. Pervyshev. A generic time hierarchy with one bit of advice. Computational Complexity, 16(2):139-179, 2007. URL: http://dx.doi.org/10.1109/CCC.2006.7.
S. Žák. A Turing machine time hierarchy. Theoretical Computer Science, 26(3):327-333, 1983. URL: http://dx.doi.org/10.1016/0304-3975(83)90015-4.