引用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).”
称赞作者把定义讲得清楚,甚至附上花体字母的拉丁对应
图同构问题可在拟多项式时间内求解,打破 1983 年的纪录
论文证明图同构(GI)及相关的字符串同构(SI)和陪集交(CI)问题可以在拟多项式时间 exp((log n)^O(1)) 内求解,此前 GI 的最好上界是 Luks 于 1983 年给出的 exp(O(√(n log n)))。算法建立在 Luks 的 SI 框架上,用群论的“局部证书”和组合式规范划分技术攻克 Luks 算法的障碍情形,并证明在明确的意义下 Johnson 图是有效规范划分的唯一障碍。
评论者称赞它把定义写得清楚,同时提醒这是拟多项式而非真正多项式时间,而且论文很新、尚未经过充分检验。
“He lays out definitions clearly and even goes as far as as presenting Latin equivalents of Fraktur letters (I wouldn't bother).”
“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.”
“or perhaps, this arxiv paper:”