按年被提到
20152015 · 4 次2026
数学、逻辑与理论›数学猜想与重大证明·arXiv:1512.03547 · cs.DS

Graph Isomorphism in Quasipolynomial Time

拟多项式时间内的图同构
László Babai · 2015

图同构问题可在拟多项式时间内求解,打破 1983 年的纪录

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 7 人首次 2015-12-14 · 最近 2022-06-10
7不同的人
4活跃月份
7讨论串
293被引(OpenAlex)

论文证明图同构(GI)及相关的字符串同构(SI)和陪集交(CI)问题可以在拟多项式时间 exp((log n)^O(1)) 内求解,此前 GI 的最好上界是 Luks 于 1983 年给出的 exp(O(√(n log n)))。算法建立在 Luks 的 SI 框架上,用群论的“局部证书”和组合式规范划分技术攻克 Luks 算法的障碍情形,并证明在明确的意义下 Johnson 图是有效规范划分的唯一障碍。

HN 为什么提它

评论者称赞它把定义写得清楚,同时提醒这是拟多项式而非真正多项式时间,而且论文很新、尚未经过充分检验。

奠基之作难度 5 / 5约 480 分钟经得起时间
读之前最好知道
1计算复杂性理论(complexity theory)
2置换群与群论(permutation groups)
3图论与图同构问题
4Luks 的群论算法

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用Eifoov7h · 2016-03

“He lays out definitions clearly and even goes as far as as presenting Latin equivalents of Fraktur letters (I wouldn't bother).”

称赞作者把定义讲得清楚,甚至附上花体字母的拉丁对应
The Global Rebellion Against “No-Skin-In-the-Game” Insiders原评论 ↗
引用openasocket · 2016-12

“Note it was actually Quasipolynomial time, not true polynomial time. It's also a pretty recent paper, so it could turn out to have flaws.”

提醒这是拟多项式时间而非真多项式时间,且论文较新可能有漏洞
An Algebra of Graphs原评论 ↗
引用gilleain · 2022-06

“or perhaps, this arxiv paper:”

给出 Babai 的这篇 arXiv 论文作为替代参考
Quantum chip takes microseconds to do task that takes a supercomputer 9k years原评论 ↗
被提交为 story · 4 次