Scholarlink

Designing algorithms for space bounded models with restoration requirements on (most of) 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 w is useful, we relax the restoration requirement: only when the content of the catalytic tape is \(w \in A \subseteq \varSigma ^*\) , the catalytic Turing machine needs to restore w at the end of the computation. We define, \(\textsf{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 prove the following for the almost-catalytic model.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Almost-Catalytic Computation

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Sagar Bisoyi,
  • Krishnamoothy Dinesh,
  • Bhabya Deep Rai,
  • Jayalal Sarma

摘要

Designing algorithms for space bounded models with restoration requirements on (most of) 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 w is useful, we relax the restoration requirement: only when the content of the catalytic tape is \(w \in A \subseteq \varSigma ^*\) , the catalytic Turing machine needs to restore w at the end of the computation. We define, \(\textsf{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 prove the following for the almost-catalytic model.