精读笔记
Problem Setting
论文标题：Verifying global identifiability of parametric linear ODE models is NP-hard（arXiv preprint / 2026-06-02）。
这篇论文不是在做新的 identifiability algorithm，而是在给 global identifiability 判定找复杂度边界。对象是参数有理依赖、状态变量线性的 ODE 系统，问题是：给定参数域 D，是否能从输入输出数据唯一恢复参数。
真正困难点不在于定义 identifiability，而在于“全局唯一性”本质上是一个函数单射性问题：只要输出方程能看到某些参数组合，是否足以唯一反推出原参数，取决于这些组合在给定 domain 上是否 injective。这个判断在实数域尤其麻烦，因为复数域里的代数生成关系不等价于实数域上的单射恢复，例如 α^3 在 R 上可逆但在 C 上不是同一意义下的 rational field recovery。
以前方法主要卡在算法工程和符号消去复杂度上：DAISY、SIAN、StructuralIdentifiability.jl 等能判定很多实例，但没有解释为什么某些实例不可避免地难。已有复杂度结果更多是 local identifiability 或复数域分析，不能直接说明 real-domain global identifiability 的 worst-case 难度。本文的关键矛盾是：identifiability 看似是微分代数问题，但其全局版本的瓶颈其实是参数映射在 domain 上的 injectivity。
Motivation
已有路线不够的原因是，它们通常把问题当成“如何更有效地消去状态变量/计算 IO-equations/计算可辨识函数字段”，但没有回答消去之后的单射判定是否本身就困难。也就是说，即使 IO-equations 很快算出来，系数映射是否能唯一决定参数仍然可能是 NP-hard 的。
作者的核心观察是：线性 ODE 的 IO-equation 系数可以被设计成任意给定多项式映射 g(α)。这使得 global identifiability 至少和 polynomial map injectivity 一样难。反过来，一般线性 ODE 的可辨识性又能通过 IO-equation 系数映射 ψ(α) 的 injectivity 来刻画。于是 complexity gap 被压缩到 injectivity problem。
关键缺口是：global identifiability over real fields 缺少复杂度定位。复数域的代数闭包简化了很多字段论问题，但应用中参数通常在 R 或受限 domain 上，且 domain-dependent injectivity 是核心。本文正是把这个缺口形式化。
Core Idea
论文真正的核心思想是把 global identifiability 从“微分系统是否能恢复参数”降维为“某个由系统诱导的参数映射是否单射”。下界构造非常直接：给定多项式映射 g=(g1,...,gn)，构造 companion-form 线性系统 x1'=x2,...,xn'=Σ gi(α)xi, y=x1。连续微分 y 后得到 y^(n)=g1(α)y+...+gn(α)y^(n-1)，因此输出能看到的恰好是 g(α)。参数可辨识当且仅当 g 在参数域上 injective。
本质区别在于，论文没有试图优化 differential elimination，而是证明 elimination 之后留下来的 injectivity 判断已经足够难。它改变了问题建模方式：从“ODE symbolic computation complexity”转为“parameter-to-invariant map injectivity complexity”。这个视角比单纯分析 Gröbner 或 characteristic set 更干净，因为它说明慢不是某个软件实现的问题，而是 global identifiability 的 worst-case 结构本身可编码 NP-hard 问题。
这里没有机器学习意义上的 inductive bias，但有一个理论上的结构性 bias：IO-equation coefficients 是系统可观测信息的充分代数摘要；global identifiability 等价于这个摘要映射是否分离参数点。
Method
1）Injectivity → identifiability 的编码。论文用 companion-form 线性 ODE 把任意多项式映射 g 嵌入 IO-equation 系数。它解决的是下界问题：证明 identifiability 至少能表达 injectivity 的困难性。为什么需要它：只有这种显式编码才能说明 NP-hardness 不是来自非线性状态动力学，而在线性 ODE 中已经存在。
2）IO-equation 系数字段刻画。通过 differential algebra，IO-identifiable functions 的字段由 IO-equation 的系数生成。它解决的是上界/等价性问题：把原始 ODE 的可辨识性转换成一个有限维参数映射 ψ 的 injectivity。核心变化是从无限 jets / differential field 中抽取有限代数 invariants。
3）实数域与有限域下的定义修正。论文不简单沿用 C 上的“α 属于输出生成字段”式定义，而是要求存在某个 h(α) 落在可观测字段中且 h 在指定 domain 上 injective。有限域/正特征下还引入 perfect closure。它解决的是字段包含关系与实际唯一恢复之间不一致的问题。
4）Unexpanded 表示控制表达式爆炸。一般线性系统消去状态变量会产生 determinant 等指数项；若强制展开，归约本身可能不再多项式。作者用 unexpanded Gaussian elimination / composed polynomial representation 保持表达紧凑。它解决的是复杂度论归约的表示问题，不是降低原问题本质难度。
Key Insight / Why It Works
最关键 insight 是：global identifiability 的本质不是“能不能求出参数公式”，而是“输出诱导的不变量是否 separating”。IO-equation coefficients 充当了不变量坐标；如果两个参数点给出相同 coefficients，那么它们产生相同 IO behavior，无法全局区分；如果 coefficient map 在 domain 上 injective，则可通过这些可观测组合唯一定位参数。
下界为什么成立：companion-form 系统把 g(α) 作为唯一出现在最高阶输出方程中的系数，Wronskian 非零保证这些系数确实可由 generic output 解出，而不是被 differential relation 混掉。因此任意 polynomial map injectivity 都能被 ODE identifiability 模拟。这是实质贡献，不是 engineering。
上界为什么成立：对线性 ODE，状态变量消去后得到 IO-equations；其系数生成的字段 k 正是 IO-identifiable information。于是参数元组可辨识等价于系数映射 ψ 是否在 domain 上分离参数点。这个机制依赖线性 ODE 的 IO-equation 理论，尤其是 [18] 类结果。对单输出 global identifiability，IO-identifiability 与 full identifiability 可对齐；多输出一般情形文中没有给出同样强的完整等价。
最可能只是辅助的是 knapsack/cube 部分。它用于给 injectivity 的 NP-hardness 一个 domain-general 的支撑，并扩展到 semi-algebraic/Zariski open/definable sets，但不是 identifiability 归约的核心。真正核心是 companion-form 编码与 IO coefficient map 等价。
这里没有 scaling、data coverage、retrieval、benchmark leakage 之类问题；这是一篇纯理论复杂度论文。若要类比，论文的“增益”不是算法性能，而是把一个看似微分代数的判定任务 representation-align 到 injectivity problem，从而得到复杂度定位。工程上可能有用的 insight 是：实际工具的瓶颈不一定在求 IO 方程，而可能在 coefficient map 的全局单射判定和表达式表示。
Relation To Prior Work
最接近的路线有两类：一类是 structural/global identifiability 的 differential algebra 工具链，包括 DAISY、SIAN、COMBOS、StructuralIdentifiability.jl，以及 Hong–Ovchinnikov–Pogudin–Yap 等关于全局可辨识性的理论；另一类是 local identifiability 的复杂度分析，例如 Sedoglavic 相关工作。本文和这些工作的本质差异是，它不提供判定算法，也不优化 Gröbner/消去，而是给 global identifiability 的 worst-case complexity 一个归约级解释。
与已有 IO-equation identifiability 工作相比，本文大量依赖其结论：IO-equation coefficients 生成可辨识函数字段。这一点不是全新数学对象。新意在于把该字段刻画用作复杂度归约的接口：一边编码 injectivity，另一边把 identifiability 还原为 injectivity。
与只在 C 上讨论 identifiability 的工作相比，本文实质新增的是 real/finite field/domain-dependent 处理。例子 α^3、α^3−α 说明 R 上的 injectivity 与 C 上的代数字段可恢复性不同。这个差异不是表面泛化，而是 global identifiability 在应用场景中的核心。
与 polynomial map injectivity 的复杂度结果相比，本文没有重新发明 injectivity NP-hardness；它把那个困难性迁移到线性 ODE identifiability。看似新的 knapsack variety/cube 构造更多是为了适配不同 ring/domain 的技术包装，实质创新仍是 ODE ↔ injectivity 的等价框架。
Dataset / Evaluation
没有实验、数据集或 benchmark；evaluation 是复杂度证明。论文的 claim 是理论性的：NP-hardness 与 co-NP_R 上界，因此不需要数值实验支持。
从验证范围看，证明覆盖状态变量线性的参数 ODE，参数有理依赖；下界甚至通过非常受限的 companion-form 单输出系统完成，说明困难性不是由复杂非线性动力学引入的。上界对 IO-identifiability 更完整，对 global identifiability 明确给到单输出情形。
是否支持核心 claim：基本支持。主结论“global/IO identifiability 与 injectivity problem 复杂度等价/相关”由双向归约支撑。不过文中对 L_gid 的完整一般多输出上界没有像 L_gioid 那样干净；因此若把标题理解成所有 global identifiability 情形都完整等价 injectivity，需要谨慎。更准确的读法是：IO-identifiability 与单输出 global identifiability 得到清晰复杂度定位，而一般 global identifiability 的边界仍有条件。
Limitation
最重要的前提是线性 ODE。虽然这已经足以证明困难性，但不能直接说明非线性 ODE 的复杂度精确层级；非线性只会更复杂是直觉，不等于形式化 tight bound。
第二个前提是表示模型。上界依赖 unexpanded 表达式，否则 IO coefficient 可能指数膨胀，例如 determinant 有 n! 项。这个处理在复杂度论上合理，但也说明实际算法中如果系统必须展开表达式，复杂度会更糟。换句话说，上界部分一定程度上把难点从“ODE 消去”转移到“紧凑表达式上的 injectivity 判定”。
第三，BSS/algebraic complexity 与实际 bit complexity 有距离。BSS 模型把域元素和基本算术当 unit cost，不能反映整数系数大小、表达式高度、数值稳定性、CAS 内存爆炸等实际瓶颈。文中未充分说明 bit-level 版本能否得到同等干净的复杂度分类。
第四，多输出 full global identifiability 的处理不完全。论文清晰证明 L_gioid ≤p injectivity，以及 L_gid,1 的对应结果；但一般 L_gid 多输出场景下 identifiability 与 IO-identifiability 的差异没有完全消掉。这是理论上限之一。
第五，domain D 的 definability/编码也很关键。若 D 结构特殊，例如低维区间、单调性约束、物理参数正性且映射具有特殊稀疏结构，worst-case NP-hardness 不自动排除高效子类算法。实际模型可能远离 worst-case，这篇论文不回答哪些 biological/control 模型族 tractable。
Takeaway
- 1）以后讨论 global identifiability 算法复杂度时，不能只看 differential elimination；即使 IO 方程已经得到，coefficient map 的 injectivity 也是核心难点。
- 2）线性 ODE 已足够表达 NP-hard injectivity，因此“限制到线性系统”并不自动带来 tractability。
- 真正可能 tractable 的方向应来自更强结构限制，例如图结构、稀疏性、monomial/toric 结构、低维参数组合，而不是线性本身。
- 3）实数域 identifiability 必须显式处理 domain-dependent injectivity。
一句话总结
这篇论文把参数线性 ODE 的全局/IO 可辨识性判定定位为 polynomial map injectivity 判定的复杂度同类问题，核心贡献不是新算法，而是证明该方向的 worst-case 难度已经在线性单输出系统中不可避免。