ETH 被驳倒后 3-SAT 有亚指数算法,图对齐问题仍难
JFPuget · x · 2026-11-07
Marc Lelarge 介绍与图同构相关的新结果:指数时间假设(ETH)被驳倒后,3-SAT 获得亚指数算法,但更难的图对齐问题(GAP)依然困难。其团队提出用一条 GNN 链来求解 GAP,并公开了代码与模型。讨论中还澄清图同构问题目前既无多项式时间解法也未被证明 NP 完全;配图给出 GAP 的形式化定义——最小化 Frobenius 范数,等价于最大化匹配边数,并可归约到哈密顿路径、最小二分、最大公共子图等 NP 难问题。
所属事件:ETH 被驳倒后 3-SAT 获亚指数算法(2 条相关)→
「研究」频道最新
- 模型看得见还是推不动？DecoyCount 等 two benchmark 拆解视觉推理错位 — AndrewDai · 2026-11-07
- ICLR 投稿撞车合作者论文,作者公开求助如何向 AC 澄清原创性 — BlancheMinerva · 2026-11-07
- BlancheMinerva 批评「等工作转正再跟进」的学术协作观有害科研 — BlancheMinerva · 2026-11-07
- 量子加速边界澄清:Aaronson-Ambainis 猜想并不限制 Shor 类超多项式加速 — thomasahle · 2026-11-07
- Flower Computers 开源发布文本语义编码器,号称速度最快 — matdryhurst · 2026-11-07
- 港科大与腾讯推出 Möbius：统一动作语言模型，0.6B 超 3B 专用模型 — bdsqlsz · 2026-11-07