图同构算法突破:运行时间指数从 2 降到 1,达 n^O(log n)
fortnow · x · 2026-11-03
MTHajiaghayi 团队宣布图同构(Graph Isomorphism)问题的改进结果:新算法运行时间为 n^O(log n),将此前最佳界中的显式指数从 2 降到 1。图同构由此与 parity、mean-payoff、随机博弈等问题同属这一运行时间类别。
引用补充了背景:Babai 2018 年的完整论文存在证明缺失和错误,其界为 exp(O((log n)^O(1)));团队借助 THEO 形式化递归得到显式指数。研究由 DARPA expMath 项目资助。
「研究」频道最新
- TraceForge 用生成式推理迹替代教师模型痕迹，Qwen3.5 pass@1 提升最高 7.1 点 — jiqizhixin · 2026-11-03
- Q-CTRL 模块化容错量子架构登上 New Journal of Physics — MJBiercuk · 2026-11-03
- Google 用 AI agent 集群修复 TPU 编译器，已解决 142 个 bug — omarsar0 · 2026-11-03
- Q Labs 新 scaling law:千亿亿参数 Transformer 训练配方出炉 — josephdviviano · 2026-11-03
- Skill++ 论文:技能库扩到 731 个,路由准确率从 36.4% 提至 76.3% — dair_ai · 2026-11-03
- CMU 首届 Protostar 挑战赛开跑:用 AI 做气候风险预测 — evijit · 2026-11-03