理论计算机科学家问 Claude：新证明中关键变量的复杂度是 Promise-BQP 完全
fortnow · x · 2026-11-11
理论计算机科学家 Lance Fortnow 对新 Aronson-Ambainis 证明中「寻找有影响力的变量」的复杂度产生好奇，于是询问 Claude。结论：若给定量子电路，该问题是 Promise-BQP 完全的；若允许对多项式做 O(log n log log n) 次查询则可解。展示了用前沿模型辅助理论 CS 研究的一个小案例。
「研究」频道最新
- DeepMind 用智能体 AI 形式化验证 Signal 加密协议，被称里程碑 — jdluk87 · 2026-11-11
- Baseten 首届 All-Gather 研究大会公布议程：Noam Brown、Oriol Vinyals 等出席 — vjkaruna · 2026-11-11
- 1960 年「末日方程」神预言:2026 年 11 月 13 日人口将趋于无穷 — csvoss · 2026-11-11
- 论文关键假设:生产率 a 随人口 N 单调增长 — csvoss · 2026-11-11
- 1960 年论文预言:2026 年 11 月 13 日人口将达无穷大 — csvoss · 2026-11-11
- 「LLM 天生不连续」是误解：token 只是连续过程的采样读数 — Sauers_ · 2026-11-11