关于结构泛化的计算复杂性

结构泛化已被多个基准反复测量，但从未被正式定义。我们给出了一个定义，将两个前提（组合结构和无界泛化）翻译成数学语言。这个定义本身是中立的：对规则进行硬编码的编译器也能满足它。但结构泛化只有在能力能够从有限数据中自主产生的情况下才成为一个科学问题。这个问题将计算下限 $\mathrm{NC}^1$ 与纯 Transformer 的可学习上限 $\mathrm{TC}^0$ 进行比较。在蒙塔哥维实例化下，每个组合规则分为两个投影：句法面（$F_γ$）和语义面（$G_γ$）。 $G_γ$ 侧的树评估是 BFVP 的实例，它是 $\mathrm{NC}^1$ 完整的（Buss，1987）。纯粹的 Transformer 必须同时学习两张脸，但 Kraus 等人。 (2026) 证明其可学习类 $\subseteq \mathrm{TC}^0$。在标准假设 $\mathrm{TC}^0 \neq \mathrm{NC}^1$ 下，纯 Transformer 无法学习结构泛化。神经符号系统之所以能够获得最佳基准分数，正是因为它们注入了 $G_γ$，从而避开了真正困难的一半。基准分数无法区分“学到的”和“给出的”。这就是本文要阐明的内容。