未解决问题，应用与计算数学, 组合数学与离散数学，1971年提出

图同构问题的计算复杂性

未解决

给定两个具有 $n = |V_1| = |V_2|$ 个顶点的有限简单图 $G_1 = (V_1, E_1)$ 与 $G_2 = (V_2, E_2)$ ，图同构问题（ $\mathrm{GI}$ ）询问是否存在双射 $\varphi : V_1 \to V_2$ ，使得 $\{u, v\} \in E_1$ 当且仅当 $\{\varphi(u), \varphi(v)\} \in E_2$ 。 $\mathrm{GI}$ 是否属于复杂性类 $\mathsf{P}$ （即确定性多项式时间 $n^{O(1)}$ ）？

提出者, 1971斯蒂芬·库克

研究前沿截至2026年

截至2026年，图同构问题是否属于 $\mathsf{P}$ 仍未解决。拉斯洛·巴拜2015–2017年的拟多项式时间算法确立了上界 $\exp((\log n)^{O(1)})$ （哈拉尔德·赫尔夫戈特进一步证明 $(\log n)^c$ 中的指数可取为 $c = 3$ ）。继巴拜的突破之后，多对数维韦斯费勒–莱曼算法（ $(\log n)^{O(1)}$ - $\mathrm{WL}$ ）及动态规划扩展相继建立，而蔡进一、菲勒与伊默曼（1992年）证明了任何固定维数的 $k$ - $\mathrm{WL}$ 检验都无法解决所有图上的 $\mathrm{GI}$ 。

已知最佳结果

巴拜（2015–2017年）：图同构问题、字符串同构问题与陪集交问题均可在确定性拟多项式时间 $\exp((\log n)^{O(1)})$ 内求解。
卢克斯（1982年）及格罗厄–诺伊恩–施韦泽（2018年）：对于最大度为 $d$ 的图，可在 $n^{\operatorname{poly}(\log d)}$ 时间内检验同构。
舍宁（1988年）： $\mathrm{GI}$ 属于低谱系 $\mathsf{Low}_2$ ，且除非多项式谱系坍缩至 $\mathsf{\Sigma}_2^{\mathsf{P}} = \mathsf{\Pi}_2^{\mathsf{P}}$ ，否则不可能是 $\mathsf{NP}$ 完全的。

使用的方法及其局限

方法	取得的结果	局限所在
卢克斯置换群分治框架与巴拜局部证书 / 设计引理	通过具有 $O(\log n)$ 递归深度的正则 $2$ 步划分，规约了约翰逊图上的巨型置换群 $S_k$ 或 $A_k$ 作用	跨越 $O(\log n)$ 层递归的乘法分支因子累积为 $n^{\operatorname{polylog}(n)}$ ，而非多项式界 $n^{O(1)}$
韦斯费勒–莱曼（ $k$ - $\mathrm{WL}$ ）颜色细化法	对几乎所有随机图以及排除固定子式的图类在多项式时间内解决同构判定	蔡进一–菲勒–伊默曼（1992年）构造的反例图迫使不结合群论陪集管理的纯组合 $k$ - $\mathrm{WL}$ 算法需要 $k = \Omega(n)$ 的维数

尚未解决的问题

图同构问题是否属于 $\mathsf{P}$ ，即能否在确定性时间 $n^{O(1)}$ 内求解？
能否将图同构问题拟多项式运行时间 $\exp(O((\log n)^c))$ 中的指数 $c$ 降至 $3$ 以下，甚至降至 $1 + o(1)$ ？

参考文献

László Babai (2016). Graph isomorphism in quasipolynomial time · DOI:10.1145/2897518.2897542 · arXiv:1512.03547
Eugene M. Luks (1982). Isomorphism of graphs of bounded valence can be tested in polynomial time · DOI:10.1016/0022-0000(82)90009-5
Uwe Schöning (1988). Graph isomorphism is in the low hierarchy · DOI:10.1016/0022-0000(88)90010-4