首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Unambiguous Catalytic Computation
  • 本地全文:下载
  • 作者:Chetan Gupta ; Rahul Jain ; Vimal Raj Sharma
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-14
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The catalytic Turing machine is a model of computation defined by Buhrman, Cleve, Kouck, Loff, and Speelman (STOC 2014). Compared to the classical space-bounded Turing machine, this model has an extra space which is filled with arbitrary content in addition to the clean space. In such a model we study if this additional filled space can be used to increase the power of computation or not, with the condition that the initial content of this extra filled space must be restored at the end of the computation. In this paper, we define the notion of unambiguous catalytic Turing machine and prove that under a standard derandomization assumption, the class of problems solved by an unambiguous catalytic Turing machine is same as the class of problems solved by a general nondeterministic catalytic Turing machine in the logspace setting.

  • 关键词:Catalytic Computation ; Logspace ; Unambiguous computation
国家哲学社会科学文献中心版权所有