Back to Search
Start Over
Catalytic space: non-determinism and hierarchy
- Source :
- Theory of Computing Systems, 62(1), 116-135. Springer New York, 33rd Symposium on Theoretical Aspects of Computer Science: STACS'16, February 17-20, 2016, Orléans, France, 33rd Symposium on Theoretical Aspects of Computer Science
- Publication Year :
- 2016
-
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.
- Subjects :
- Discrete mathematics
000 Computer science, knowledge, general works
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Hierarchy (mathematics)
Computation
Model of computation
0102 computer and information sciences
02 engineering and technology
Computer Science::Computational Complexity
Space (mathematics)
01 natural sciences
Theoretical Computer Science
Combinatorics
Set (abstract data type)
Computational Theory and Mathematics
010201 computation theory & mathematics
Theory of computation
Computer Science
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
Auxiliary memory
Complement (set theory)
Mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 14324350
- Database :
- OpenAIRE
- Journal :
- Theory of Computing Systems, 62(1), 116-135. Springer New York, 33rd Symposium on Theoretical Aspects of Computer Science: STACS'16, February 17-20, 2016, Orléans, France, 33rd Symposium on Theoretical Aspects of Computer Science
- Accession number :
- edsair.doi.dedup.....2c797a80db4cc40c2541abf89fbfbf33