问题
图同构 GI 的复杂度地位：在 NP 但既无多项式算法、也无 NPC 证据（经交互证明系统，GI ∉ NPC 除非 PH 塌缩）。Babai 2015 的准多项式（exp(logO(1)n)）算法把 GI 推到 «准多项式»。算法核心是置换群论：若尔当型 «障碍组» 的递归消除。问题：这个群论内核能否彻底消除、给出 P 算法？或证明 GI ∉ P？
主要概念
Luks 框架与若尔当障碍
Luks 1982：度受限图的 GI 在 P（对度 d，复杂度 nO(d)）——算法沿 «自同构群的轨道递归»，关键在于 «置换群中的 «障碍» 子群»（Jordan 型： «大轮换+小支撑» 结构）的 «可识别与可分裂»。一般图的自同构群是 Sn 的任意子群—— «完整置换群宇宙» 使递归失控。Babai 的 «局部证明»（个体化–递归）：固定 «桶» 结构，把障碍压到 «若尔当型»—— «大轮换+指数小支撑» 的 BCnn 型组，经组合 «设计» 论证消除。
组合 vs 群论的分工
算法两臂：①«组合» 臂（桶、设计、强正则图的 «排除»）；②«群论» 臂（障碍组的递归消除）。两臂交接在 «若尔当型» 障碍： «大轮换» 给出 «强正则» 结构（Johnson 型方案的 «成块» 组合），设计论证排除 «多数» 情形。
主要命题与证明
命题 1（Luks 度受限定理，完整骨架） 度 ≤ d 图的 GI 在 nO(d)。骨架：归约到 «自同构群的轨道–稳定子» 递归；障碍 «对称群 Sk 作用在 k 元组上» 由度限制排除（ Sk 作用含 «高对称» 局部结构 ⟹ 度 > d）。□
命题 2（Babai 准多项式的群论核心，完整骨架） ①«个体化–递归»：固定 log n 个点的 «颜色»，自同构群被压到 «障碍组族»；②«障碍组» 是若尔当型（大轮换 k-轮换 + 支撑 ≤ exp(√log n) 型）；③«设计论证»： Johnson 方案的 «成块» 结构在 «颜色数足够大» 时唯一化 ⟹ 障碍可 «裂开»。复杂度 exp(O(logcn))，当前 c = 3（Babai 原版）到 2 的改进（后续优化）。□
命题 3（两条开放路，诚实评估） ①«深层若尔当消除» 路线：把障碍组族压得更小（ «轮换长度» 与 «支撑» 的同时控制）——若完全消除，GI ∈ P 随之；当前障碍：Johnson 型 «成块» 结构在 «设计» 条件下不能被进一步排除（«成块» 是群论与组合的 «交接面»，二者都顶到）。②«证明 GI ∉ P» 路线：需要 «复杂度理论» 的 «自然证明» 类障碍（经交互证明系统与电路复杂度），当前完全无路径。结论：两路的困难都落在 «置换群的表示论与组合的接口»——GI 的复杂度地位是 «群论算法学» 的终极试金石。□
进展与文献
Babai《Graph isomorphism in quasipolynomial time》（STOC 2016，arXiv 2015 的 84 页版本与后续修正——Helfgott–Seress 对 «Group membership» 部分的修正已被 Babai 吸收）；Luks 1982（度受限）；Neuen–Schweitzer 的 «乘性重复率» 精修；Helfgott–Le Gall–... 的 «GI 与群论» 综述。开放核心：准多项式到多项式的 «最后一步»，以及 GI 是否 «本质上» 需要 «非群论» 思想。