问题
图同构（GI）：给定 G, H，问存在双射 φ: V(G) → V(H) 保邻接吗？Babai 2015（2017 修正）证明 GI ∈ 准多项式时间 exp((log n)O(1))——把 Luks 1983 以来的指数纪录一次性打破。GI 是否在 P 中仍开放。
主要概念
Babai 机器的三步
①族分裂：把输入图的 «关联结构» 分为 «单块»（大 Johnson 型单元）与 «均匀块»（小块的规则拼装）—— «组合结构定理»（ «图的结构不能太乱» 的有限版）。②局部证书：单块用 Johnson 群的 «深度优先» 群论（ «组合群论» 传统），均匀块用 «递归分裂 + 群积»。③巨集编码： «关键障碍» 是 «同构把巨集怎么搬»—— «信息论 » 技巧：设计 «判别器»，使 «错误搬法» 在多项式时间内 «露出»。
为什么 «不是 NP 完全» 的共识
GI ∈ SPP（Babai–Fortnow–... 的 «AM ∩ coAM» 超集链）；若 GI NP-完全则多项式层级塌缩——多数理论家以此认为 GI 不 NP-完全。 «NP 中间 » 的候选（Ladner 定理保证存在 «假设 P≠NP»）中 GI 是结构最好的一个。
主要命题与证明
命题 1（Luks 1983 定理） 度 ≤ d 的图同构可在多项式（nO(d)）时间判定。
梗概 «轨道–稳定 » 归约：逐点 «锚定»，每步把 «同构集合» 收窄为 «陪集»； «陪集交» 计算依赖 «置换群的点稳定子链»——度 ≤ d 保证 «稳定子 » 是 «小幅» 群（属于 «深度 ≤ d» 的 « состава类 » 组合群论类），其 «陪集交» 多项式可解。□
命题 2（Babai 准多项式定理骨架） GI ∈ exp((log n)O(1))。机器： «结构定理 → 分裂树深 O(log n) → 每层 «局部证书» 用 «Johnson 捆绑 » 群的 «深度优先»（ «多项式 × 深度» = 准多项式）。
命题 3（AM 协议） GI ∈ AM：Arthur 随机选 φ 或 «置换», Merlin 回答 «哪边»—— «非同构 » 的交互证明（ «GI 的补在 AM»）给出 «GI 不太可能 NP-完全» 的实质证据。□
进展与文献
Babai 2015/2017（Turing 讲座稿）；Luks 1983（FOCS/JCSS）；Helfgott–Bajpai–Dona 的 «平滑化» 与简化证明系列；Neuen–Schweitzer 的 «深度优先» 重构与实验验证；Grohe–Neuen 的 GI 专著《The Graph Isomorphism Problem》。开放核心：P 算法是否在 «分裂树深度压到 O(1)» 或 «巨集编码强化» 中出现； «GI 的低维受限版»（ «树宽 ≤ w» 已线性、 «有界度» 已多项式）的 «中间参数» 全景图。