Options
On Pure Space vs Catalytic Space
Date Issued
01-01-2020
Author(s)
Abstract
This paper explores the power of catalytic computation when the catalytic space (c(n), the full memory for which the content needs to be restored to original content at the end of the computation) is much more than exponential in the pure space (s(n), the empty memory which does not have any access/restoration constraints). We study the following three regimes of the relation between s(n) and c(n) and explore the class in each of them. Low-end regime: We define the classes and (nondeterministic variant of) where and. Exploring the connection between computational power of one counter machines (OC) and constant pure space catalytic Turing machines, we observe that and show that. We prove that Low-end non-constant regime: Let M be an oblivious catalytic Turing machine using s(n) pure space and c(n) catalytic space such that then L(M) is regular. This strengthens the classical theorem on to the case of catalytic Turing machines.High-end regime: We show an implementation of incremental dynamic program using catalytic machines, thus showing that Knapsack problem (with n items, sum of their costs as C and the capacity of the bag as K) can be solved in pure space and catalytic space. Hence, catalytic algorithms can lead to a non-trivial saving in the pure space required for computation when K is. Our techniques include interesting generalizations of crossing sequence arguments and implementations of incremental dynamic programs using catalytic algorithms. These may be of independent interest.
Volume
12337 LNCS