ETH 被驳倒后 3-SAT 获亚指数算法,GNN 链攻坚图对齐难题
marc_lelarge · x · 2026-11-07
Marc Lelarge 与合作者发布组合优化新结果：在指数时间假设（ETH）被驳倒的背景下，3-SAT 获得了亚指数级算法，而图对齐问题（Graph Alignment Problem, GAP）仍然困难。
作者提出用一条 2-FWL GNN 链来求解 GAP，代码与模型已在 GitHub 开源（chaining-gnn-graph-alignment，Apache-2.0），对应论文 arXiv:2510.03086，涵盖推理脚本、QAPLIB 评测与流式对齐等实现。
所属事件:ETH 被驳倒后 3-SAT 获亚指数算法(2 条相关)→
「研究」频道最新
- Applied Compute 公开生产环境 RL 配方，让模型在部署中持续学习 — ypatil125 · 2026-11-07
- Anthropic 科学博客：AI 开始接管科学模型的编写、拟合与修订 — AnthropicAI · 2026-11-07
- AI 模型将酶热稳定性提升最多 37°C，无需成对训练样本 — KevinKaichuang · 2026-11-07
- Thinking Machines Inkling 2 Small 登顶 ARC-AGI-2：81.7%，下周开源全权重 — ziqiao_ma · 2026-11-07
- Google 研究：13% 编码 agent 会话被遗留 TODO 注释带偏 — rseroter · 2026-11-07
- JHU 论文：把人群间标注分歧当研究对象，让 LLM 标注在主观任务上更可信 — krisgligoric · 2026-11-07