.png){kind=icon}
返回
Derandomizing Logspace With a Small Shared Hard Drive
.png){kind=icon}
OA
AI
DOI：10.1007/s00037-025-00275-6.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们为空间有界随机性归约获得了新的催化算法。在(Buhrman, Cleve, Koucký, Loff, and Speelman STOC 2013)引入的催化计算模型中，我们被赋予一个小的工作磁带和一个具有任意初始配置的更大的催化磁带。我们可以编辑该磁带，但在计算完成时必须精确恢复其初始配置。我们证明$$BPSPACE[S] \subseteq CSPACE[S,S^2]$$，其中$$BPSPACE[S]$$对应于随机空间S计算，而$$CSPACE[S,C]$$对应于使用O(S)位工作空间和O(C)位催化空间的催化算法。此前仅已知$$BPSPACE[S] \subseteq CSPACE[S,2^{O(S)}]$$。事实上，我们证明了一个通用的权衡关系，即对于每一个$$\alpha \in [1,1.5]$$，有$$BPSPACE[S] \subseteq CSPACE[S^\alpha,S^{3-\alpha}]$$。我们没有使用先前催化计算工作中的代数技术。相反，我们开发了一种基于催化磁带是否条件随机的分支算法，并在递归框架中实例化了这个基本元素。我们的结果给出了(Cai, Chakaravarthy, and van Melkebeek, Theory Comput. Sys. 2006)关于$$BPSPACE[S]$$的最佳已知时空权衡的一个替代证明。最后，我们将结果扩展以解决$$CSPACE[S,S^2]$$中的搜索问题。据我们所知，这是对催化计算模型中搜索问题的首次研究。
Keyword:
Pseudorandomness
Catalytic Computing
Logspace
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
1
论文数:
15
被引数:
0
机构
暂无机构信息
引用论文
.png){kind=icon}
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
PREAI
分享收藏
查看更多内容