OpenAI 单带图灵机模拟结果隐含 RAM 时间 SPACE[t^4/5] 推论
KortenOliver · x · 2026-10-07
网友 KortenOliver 指出，OpenAI 论文中的单带图灵机模拟结果（假设正确）可以直接推出：RAM 时间 t 的计算可放进 SPACE[t^(4/5)] 空间内。他疑惑论文作者为何没有在文中提到这个推论，并表示这正是他提问的初衷。随后 Ryan Williams 在回复中补充承认自己最初推文漏了一个 polylog 因子。
KortenOliver · x · 2026-10-07
网友 KortenOliver 指出，OpenAI 论文中的单带图灵机模拟结果（假设正确）可以直接推出：RAM 时间 t 的计算可放进 SPACE[t^(4/5)] 空间内。他疑惑论文作者为何没有在文中提到这个推论，并表示这正是他提问的初衷。随后 Ryan Williams 在回复中补充承认自己最初推文漏了一个 polylog 因子。