Almost-catalytic Computation

Understand

Designing algorithms for space bounded models with restoration requirements on the space used by the algorithm is an important challenge posed about the catalytic computation model introduced by Buhrman et al.

• (2014).
• Motivated by the scenarios where we do not need to restore unless is useful, we define $ACL(A)$ to be the class of languages that can be accepted by almost-catalytic Turing machines with respect to $A$ (which we call the catalytic set), that uses at most $c\log n$ work space and $n^c$ catalytic space.
• We show that if there are almost-catalytic algorithms for a problem with catalytic set as $A \subseteq \Sigma^*$ and its complement respectively, then the problem can be solved by a ZPP algorithm.