Krohn–Rhodes 复杂度的可判定性 · 公开问题 22

问题

Krohn–Rhodes 主定理（1965）：任何有限半群 S 可由 «群与 3-元组翻转变换» 的 wreath 乘积分解——更精确地，S 整除若干 «单群 wreath aperiodic 变换独异点» 的乘积。复杂度：分解中 «群层» 的最少层数（aperiodic 层不计）。问题：给定有限半群（乘法表），其精确复杂度可计算吗？目前连 «复杂度 ≤ k» 对每个固定 k 的可判定性都未证（对 k = 1 的 «aperiodic 判定» 是 Schützenberger 的 star-free 定理，可判定；k = 2 起整层开放）。这是理论计算机科学与代数的接口大题：复杂度层级对应 «正则语言的层级»（Straubing–Thérien 纲领），其可判定性与 25 号（dot-depth 2）同源。

主要概念

wreath 乘积与层级语义

wreath 乘积 W ≀ V： «V-索引的 W 族» 的变换独异点（级联自动机的代数化）。Krohn–Rhodes：变换半群 T 整除 G₁ ≀ A₁ ≀ ⋯ ≀ G_r ≀ A_r（G 单群、A aperiodic 变换独异点）；最小 r 是复杂度。语言的语义：复杂度 ≤ k 的 «语言类» 构成层级（正则语言的 «群复杂度» 层级），第 0 层 = aperiodic ⟺ star-free（Schützenberger–McNaughton–Papert），第 1 层以上逐层对应 «循环模块»——层级严格（46 号）但可判定性逐层失守。

可判定性空白的结构

«复杂度 ≤ 1»（«S 的 «群化» 只需一层»)的判定涉及 «S 的极大子群在 wreath 分解中的 «合并»»——Eilenberg 的 «变体» 问题（ «复杂度的良定义性»：不同分解路线是否给出相同 r）长期争论后由 Krohn–Rhodes–Tilson 的 «复杂度唯一性»（对变换半群）解决一半（ «holonomy 分解» 给出规范值）； «计算规范值» 的算法化是空白：候选方法（ «局部检查»、 «子半群枚举»）都在 «组合爆炸» 处失速。

主要命题与证明

命题 1（Schützenberger 的 star-free 判定，1965；陈述）　有限独异点 M aperiodic（所有极大子群平凡）⟺ 其识别语言 star-free（无星正则表达式）⟺ FO[<] 可定义。此判定可算法化（乘法表的 «H-类群检查» 直接多项式），是层级第 0 层的可判定性。

机制说明　Schützenberger 定理是 «代数 ⟹ 逻辑» 的原型：aperiodicity（乘法表上直接可查）⟺ star-free（语法条件）⟺ FO 一阶可定义（逻辑条件）。三线各自的 «算法化» 都成熟；层级第 k 层（k ≥ 1）的 «代数条件» 至今没有找到 «乘法表上可查» 的形式——这是可判定性空白的技术根源。□

命题 2（复杂度的下界与上界工具；陈述）　（i）下界： «复杂度 ≥ k+1» 的证明工具（ «块乘积的 «群容量» 计数»、Henckell–Rhodes 型 «子群配置» 下界）；（ii）上界：显式分解的构造（holonomy 分解算法——给出某个 r 但不必最优）；（iii） «规范复杂度» 的唯一性（Krohn–Rhodes–Tilson：holonomy 分解的层数是良定义的不变量，对变换半群）；（iv） «计算规范值» 的可判定性：对所有 k ≥ 2 开放。

现状说明　空白的精确形状： «复杂度 ≤ k» 的判定对固定 k 是 «有限可公理化» 的候选问题——层级语言侧对应 «dot-depth k+1 类的可判定性»（25 号同型）；已知的 «不可判定性» 结果一个都没有（与 «一阶理论的不可判定» 不同，这里连否定结果都缺），问题处于 «两头都不确定» 的罕见状态。□

命题 3（与电路复杂度的挂钩；陈述）　复杂度层级与 «AC⁰ 的代数刻画» 直接挂钩：aperiodic ⟺ AC⁰（FO）常深度；更高层对应 «depth-d 电路 + MOD 门» 的精确谱（Barrington 的 «MOD_p 电路 ⟹ 群复杂度» 桥）。因此复杂度可判定性的进展会直接转化为电路复杂度的新分层工具——反之亦然。

现状说明　Barrington 定理（1989）：宽度 5 的分支程序 = NC¹—— «群变换的级联能力» 的惊人展示；它与 Krohn–Rhodes 复杂度的联合研究（ «bounded-width branching programs 的代数»）是现代接口的主线之一。□

进展与文献

Krohn–Rhodes《Algebraic theory of machines》（1965–）；Eilenberg《Automata, Languages and Machines》B 卷（wreath 与变体理论）；Tilson 的 holonomy 与复杂度唯一性；Henckell–Rhodes 的下界工具；Straubing《Finite Automata, Formal Logic, and Circuit Complexity》（专著，接口综述）。开放核心：固定 k ≥ 2 的可判定性； «规范复杂度» 的算法化；与 24、25、45 号的联合 «可计算性地图»。