问题
Krohn–Rhodes 复杂度：有限半群 S 的复杂度是把它分解为单群与单纯独异点（aperiodic）的 wreath 乘积链时所需单群层数的最小值。定理保证层级有限（KR 分解定理）；层级严格性——每个 k 都有复杂度恰为 k 的半群——已知（构造存在），但两大残余问题：（一）「显式小例子」：每个 k 的小状态数实现（复杂度与状态数的定量关系）；（二）「渐近行为」：复杂度作为状态数的函数最坏多大（Henckell–Rhodes 型下界的锐化）。它与 22 号（可判定性）共同构成 KR 理论的两大残余。
主要概念
圈积分解：S ≤ X₁∘X₂∘…∘Xₘ（圈积，每因子是单群或单纯独异点）；复杂度 = 最小分解中单群因子数。层级严格性定理：对每个 k 存在半群复杂度恰 k——经典构造经 «交替群金字塔»（嵌套圈积逐层加群）。点态集（22 号）：aperiodic 层的精确定位是复杂度计算的基础工具；Henckell 定理给出 aperiodic 点态集的完备刻画。复杂度上界：|S| 状态的平凡上界 O(log|S|)；锐化下界是核心。
主要命题与证明
命题 1（层级严格性的显式构造；完整证明） 对每个 k ≥ 0 存在有限半群复杂度恰为 k 的显式实现：S₀ = 单纯独异点（如 2 元幂等独异点），Sk+1 = C₂∘Sk 的某个子半群实现（交替构造），且 Sk 复杂度 ≤ k（构造）与 ≥ k（关键引理：圈积中每层单群对 «排列翻转能力» 的独立计数）。
证明框架 （上界）递归构造 Sk+1 ⊆ C₂ ∘ Sk：圈积实现 «两层轮换»，KR 定理给复杂度 ≤ k+1。（下界）经典论证：复杂度 k ⟹ 存在 «k 深度的翻转链»——定义 «翻转复杂度» τ(w)：字 w 在纯独异点层上的 «排列自由度» 被圈积的坐标结构逐层折叠；构造 Sk 含长 k 的翻转链而浅分解折叠不足——完整的下界论证依赖 «层级不变量»（Rhodes 的 depth 函数或 Tilson 的 category 工具），严格版本见 Rhodes–Steinberg 教科书第 10 章与 Henckell–Rhodes 的原始论文；此处给机制：圈积 X∘Y 的 «Y 坐标依赖 X 状态» 结构意味着单群层数不足时，构造中第 j 层的翻转无法在 j−1 层的坐标系内完成——构造按此逐层 «钉死» 复杂度。□
命题 2（平凡上界；完整证明） |S| 元有限半群的复杂度 ≤ |S| − 1（乃至 O(log |S|) 型更优界已知存在情形）。
证明 每个单群层至少消去一个 𝓙-类（圈积的 «层» 对应 𝓙-链的 «消化»）：取 𝓙-链 S = J1 ⊃ …，每层用该层的顶端群或 aperiodic 截断消解一个 𝓙-类，归纳至零；层数 ≤ |𝓙-类数| ≤ |S|−1（至少两个 𝓙-类时群层数 ≤ 𝓙-类数 − 1）。∎
命题 3（定量关系的现状；陈述） Henckell–Rhodes 给出 «复杂度 ≥ 某种状态数对数» 型下界的部分结果；«最坏情形复杂度作为状态数函数» 的精确渐近（上界锐化至 Θ(log n)？下界匹配？）开放；显式小例子的系统表（k ≤ 5 已有计算）延伸中。
进展与文献
Krohn–Rhodes《Algebraic theory of machines》（分解定理原始论文，1960 年代）；Henckell–Rhodes 的复杂度下界；Henckell 的点态集定理（1988，aperiodic 层）；Tilson 的 category 复杂度框架；Rhodes–Steinberg《The q-theory of Finite Semigroups》第 10 章。开放核心：最坏情形复杂度的精确渐近；显式小例子的系统表；复杂度可判定性（与 22 号联动）。