判定两个有限图是否同构的问题在计算复杂度上被认为在P和NP之间,不知道它是否能在多项式时间内解决还是一个NP完全(或简称NPC)。

芝加哥大学的匈牙利籍数学和计算机科学教授László Babai将在11月10日发表演讲,谈论一个算法能在拟多项式时间内解决图同构问题。

László Babai曾先后获得过哥德尔奖和高德纳奖,他发表过180多篇论文。他的最新算法使得图同构问题的计算复杂度略高于P。他的结论是基于有限单群分类

(中文摘要来自Solidot

2 收藏


直接登录

推荐关注