← 研踪 PaperTrailarXiv:2611.17690 · v1
Simulating Space Bounded Read-$k$ PTMs with Space Bounded Read-Once PTMs
首次提交 2026-11-13 11:16
版本更新 2026-11-13 11:16
雷达观测 2026-11-17 04:57
摘要
We show that read- Probabilistic Turing Machines with bounded space and running time can be simulated by read-once Probabilistic Turing Machines with error , running in space and time . As a direct consequence we show that read- is equal to , for any constant . Recently OpenAI announced that . If this is true then our result immediately implies that read- is equal to .
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-13 11:16 · 最新观测版本
Simulating Space Bounded Read-$k$ PTMs with Space Bounded Read-Once PTMs
We show that read- Probabilistic Turing Machines with bounded space and running time can be simulated by read-once Probabilistic Turing Machines with error , running in space and time . As a direct consequence we show that read- is equal to , for any constant . Recently OpenAI announced that . If this is true then our result immediately implies that read- is equal to .
查看此版本解读 →查看此版本原文 ↗