OpenAI 单带图灵机模拟可推出新结论:RAM 时间 t 落入 SPACE[t^4/5]
rrwilliams · x · 2026-10-07
Ryan Williams 指出,OpenAI 的单带图灵机(tape TM)模拟结果(假设正确)可直接推出一个未被提及的推论:RAM 模型下时间为 t 的算法,其空间复杂度落在 SPACE[t^{4/5}]。他表示这正是他此前提问的初衷,不理解 OpenAI 为什么没有提到这个推论。
所属事件:OpenAI图灵机模拟结果被指隐含RAM空间复杂度新推论(3 条相关)→
「研究」频道最新
- NYU 提出 CIA 指标：LLM 思维链仅 44.8%-75.9% 反映内部计算 — newyorkuniversity · 2026-10-07
- 牛津 AI Theorist 自主破解 α-RuCl₃ 光谱之谜，AI4Science 里程碑 — Oxford · 2026-10-07
- HERMES 用可执行 Dev-Primitives 提升 SWE agent 成绩 12.4% — Haibo Jin · 2026-10-07
- 高通投机执行法：端侧语音助手响应延迟中位数降至 4.60 秒 — Qualcomm-AI-Research · 2026-10-07
- UnAct：免梯度机器遗忘，仅需 5 张图误差仅 0.21 点 — GAASH-Lab · 2026-10-07
- ALIVE 让视频插入物体「活起来」，交互指标超基线 43.9% — university-of-rochester · 2026-10-07