2024/09/11 by Sagar Bisoyi, Bisoyi, Sagar, Krishnamoorthy Dinesh +5 · 3 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Computational Complexity (cs.CC) #DNA and Biological Computing #Distributed systems and fault tolerance #FOS: Computer and information sciences #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.2409.07208
openalex publication_date 2024/09/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 clog n work space and nc catalytic space. We show that if there are almost-catalytic algorithms for a problem with catalytic set as A ⊆ Σ^* and its complement respectively, then the problem can be solved by a ZPP algorithm. Using this, we derive that to design catalytic algorithms, it suffices to design almost-catalytic algorithms where the catalytic set is the set of strings of odd weight (PARITY). Towards this, we consider two complexity measures of the set A which are maximized for PARITY - random projection complexity (\cal R(A)) and the subcube partition complexity (\cal P(A)). By making use of error-correcting codes, we show that for all k ≥ 1, there is a language Ak ⊆ Σ^* such that DSPACE(nk) ⊆ ACL(Ak) where for every m ≥ 1, R(Ak ∩ \0,1\m) ≥ (m)/(4) and P(Ak ∩ \0,1\m)=2m/4. This contrasts the catalytic machine model where it is unclear if it can accept all languages in DSPACE(log1+ε n) for any ε> 0. Improving the partition complexity of the catalytic set A further, we show that for all k ≥ 1, there is a Ak ⊆ \0,1\^* such that DSPACE(logk n) ⊆ ACL(Ak) where for every m ≥ 1, R(Ak ∩ \0,1\m) ≥ (m)/(4) and P(Ak ∩ \0,1\m)=2m/4+Ω(log m).