minilek 追问 PPSZ 类算法：已知 2^(-εn) 亚指数算法能否归入一个自然算法类
minilek · x · 2026-10-29
MIT 研究员 minilek 与 @rrwilliams 讨论细粒度复杂度（SETH 相关）问题。他询问：目前已知的所有 (2-eps)^n 时间亚指数算法（如 PPSZ 类算法），是否能被某个宽泛而自然的算法类同时涵盖？
背景要点：
- 对某些受限算法类，已有证明说明其中不可能出现 2^{o(n)} 的算法（存在类内下界）。
- 但目前尚不清楚已知最好的理论算法是否真的能被统一刻画在一个自然算法类内。
- 讨论中引用了 Claude 的回答，作者怀疑 AI 的解释可能有误。
这是一条偏理论计算机科学的学术对话，尚未有明确结论。
所属事件:Williams 与 minilek 辨析 ETH:已知 SAT 算法与下界的关系(6 条相关)→
「研究」频道最新
- AReA 免训练方法让 Qwen Image、Flux 出 6K 大图 — linoy_tsaban · 2026-10-29
- 研究发现 Llama 隐状态呈 3D 螺旋,暗合元素周期表结构 — burny_tech · 2026-10-29
- 研究者窥探 Mamba 神经元:可定位并放大单个词的触发机制 — burny_tech · 2026-10-29
- Apple 招 PhD 实习生，主攻视频 LLM 的落地推理与端侧模型 — HildeKuehne · 2026-10-29
- NeurIPS 新工作 MASEM:面向目标条件 RL 的多样化机器人状态采样 — KyleMorgenstein · 2026-10-29
- 无需读论文：四步用本地小模型和 Claude 玩转 mech-interp — burny_tech · 2026-10-29