pith. sign in

arxiv: 2606.00412 · v1 · pith:IDBEF43Pnew · submitted 2026-05-29 · 💻 cs.CC · cs.SY· eess.SY· math.AG· math.OC

Verifying global identifiability of parametric linear ODE models is NP-hard

Alexey Ovchinnikov , Pedro Soto This is my paper

Pith reviewed 2026-06-28 19:01 UTC · model grok-4.3

classification 💻 cs.CC cs.SYeess.SYmath.AGmath.OC
keywords global parameter identifiabilitylinear ODE modelscomputational complexityinjectivity problemNP-hardparametric models
0
0 comments X

The pith

Checking global identifiability of parametric linear ODE models is equivalent to the injectivity problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes the computational complexity of verifying global parameter identifiability for parametric ODE models that depend linearly on state variables and rationally on parameters over the reals. It proves this verification task is equivalent to the injectivity problem. A reader would care because identifiability checks are a required step before numerical parameter estimation, and knowing the exact complexity explains why existing algorithms can run slowly.

Core claim

For ODE models depending linearly on the state variables and rationally on the parameters over the real numbers, the problem of verifying global parameter identifiability from input-output data is equivalent to the injectivity problem.

What carries the argument

The equivalence between global identifiability verification and the injectivity problem for the parameter-to-output map.

Load-bearing premise

The ODE models must depend linearly on the state variables and rationally on the parameters over the real numbers.

What would settle it

A concrete linear ODE model where global identifiability holds but the corresponding map fails to be injective, or the reverse, would disprove the claimed equivalence.

read the original abstract

Global parameter identifiability is a property of a parametric ODE model to recover the parameter values uniquely from the input-output data. Not all parametric ODE models have this property, and checking for parameter identifiability is a prerequisite to perform numerical parameter estimation. There are many algorithms and software packages for global parameter identifiability, and frequently the runtime is large. However, the computational complexity for this problem has not been analyzed yet, though there are complexity results for local (finitely many values fit the data) parameter identifiability. In this paper, we estimate the complexity of checking global parameter identifiability over real fields for ODE models that depend linearly on the state variables and rationally on the parameters. In particular, we prove that it is equivalent to the injectivity problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims that, for parametric ODE models linear in the state variables and rational in the parameters over the reals, the problem of verifying global parameter identifiability is equivalent to deciding injectivity of a rational map; this equivalence is used to conclude that the identifiability problem is NP-hard.

Significance. If the claimed equivalence holds and the reduction preserves the model class, the result would be significant: it supplies the first complexity lower bound for global identifiability in this restricted but practically relevant ODE class, explaining the observed high runtimes of existing algorithms and motivating the development of restricted or heuristic methods.

major comments (2)
  1. [reduction construction following main theorem] The central claim rests on an equivalence between global identifiability and the injectivity problem. The reduction construction (detailed after the statement of the main theorem) must map arbitrary injectivity instances to ODE systems whose right-hand sides remain strictly linear in the state vector x. If any step introduces terms nonlinear in x, the resulting instances fall outside the stated model class and the NP-hardness result does not transfer.
  2. [proof of equivalence] The abstract asserts a proof of equivalence, yet the provided manuscript text does not contain the full sequence of steps that establish both directions while preserving linearity in x and rationality in the parameters. Without these explicit steps, the support for the load-bearing claim cannot be verified.
minor comments (2)
  1. Clarify the precise definition of the injectivity problem being reduced from (e.g., injectivity of a rational map over the reals) and state any field or domain restrictions explicitly.
  2. [introduction] Add a short paragraph contrasting the new global-identifiability hardness result with the existing complexity results for local identifiability mentioned in the introduction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable feedback on our manuscript. We address the major comments point by point below.

read point-by-point responses

  1. Referee: [reduction construction following main theorem] The central claim rests on an equivalence between global identifiability and the injectivity problem. The reduction construction (detailed after the statement of the main theorem) must map arbitrary injectivity instances to ODE systems whose right-hand sides remain strictly linear in the state vector x. If any step introduces terms nonlinear in x, the resulting instances fall outside the stated model class and the NP-hardness result does not transfer.

    Authors: The reduction construction is carefully designed to ensure that the resulting ODE systems are strictly linear in the state vector x. As detailed after the main theorem, we encode the injectivity instance into a matrix A( heta) with rational entries in the parameters heta, setting the right-hand side to A( heta) x. No nonlinear terms in x are introduced at any step, thereby preserving the model class of linear ODEs with rational parameter dependence. revision: no

  2. Referee: [proof of equivalence] The abstract asserts a proof of equivalence, yet the provided manuscript text does not contain the full sequence of steps that establish both directions while preserving linearity in x and rationality in the parameters. Without these explicit steps, the support for the load-bearing claim cannot be verified.

    Authors: We agree that the equivalence proof would benefit from a more detailed exposition. In the revised version, we will provide the complete sequence of steps establishing both directions of the equivalence, with explicit checks that linearity in x and rationality in the parameters are maintained throughout. revision: yes

Circularity Check

0 steps flagged

No circularity; equivalence proved via reduction to external injectivity problem

full rationale

The paper's central claim is a direct equivalence proof between global identifiability verification for the stated class of linear ODE models and the injectivity problem. This is an external computational problem, not derived from the paper's own definitions, fitted parameters, or self-citations. The derivation is therefore self-contained as a standard complexity reduction and does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review based on abstract only; no free parameters, invented entities, or non-standard axioms are mentioned. The result relies on standard notions from computational complexity over the reals.

axioms (1)
  • standard math Standard definitions and hardness results for the injectivity problem over real numbers
    The equivalence transfers hardness from injectivity; invoked implicitly by the claim of equivalence.

pith-pipeline@v0.9.1-grok · 5700 in / 1126 out tokens · 50666 ms · 2026-06-28T19:01:04.611545+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 13 canonical work pages

  1. [1]

    Arora and B

    S. Arora and B. Barak.Computational complexity: a modern approach. Cam- bridge University Press, 2009

    2009

  2. [2]

    E. C. Balreira, O. Kosheleva, and V . Kreinovich.Algorithmics of Check- ing whether a Mapping Is Injective, Surjective, and/or Bijective, pages 1–7. Springer International Publishing, Cham, 2014. URLhttps://doi.org/ 10.1007/978-3-319-04280-0_1

    work page doi:10.1007/978-3-319-04280-0_1 2014

  3. [3]

    Bellu, M

    G. Bellu, M. P. Saccomani, S. Audoly, and L. D’Angi`o. DAISY: A new soft- ware tool to test global identifiability of biological and physiological systems. Computer Methods and Programs in Biomedicine, 88(1):52–61, 2007. URL http://dx.doi.org/10.1016/j.cmpb.2007.07.002

    work page doi:10.1016/j.cmpb.2007.07.002 2007

  4. [4]

    Bessonov, I

    M. Bessonov, I. Ilmer, T. Konstantinova, A. Ovchinnikov, G. Pogudin, and P. Soto. Faster Gr¨obner bases via domain-specific ordering in parameter iden- tifiability of ODE models. 2023. URLhttps://arxiv.org/pdf/2202. 06297.pdf

    2023

  5. [5]

    Blum.Complexity and real computation

    L. Blum.Complexity and real computation. Springer Science & Business Media, 1998

    1998

  6. [6]

    D. A. Cox, J. Little, and D. O’Shea. Ideals, varieties, and algorithms - an introduction to computational algebraic geometry and commutative algebra (2. ed.). InUndergraduate Texts in Mathematics, 1997. URLhttps://api. semanticscholar.org/CorpusID:35416675

    1997

  7. [7]

    R. Dong, C. Goodbrake, H. Harrington, and P. G. Differential elimination for dynamical models via projections with applications to structural identifiabil- ity.SIAM Journal on Applied Algebra and Geometry, 7(1):194–235, 2023. URLhttps://doi.org/10.1137/22M1469067. 17

    work page doi:10.1137/22m1469067 2023

  8. [8]

    Gerbet and K

    D. Gerbet and K. R ¨obenack. An algebraic approach to identifiability.Algo- rithms, 14(9):255, 2021. URLhttps://doi.org/10.3390/a14090255

    work page doi:10.3390/a14090255 2021

  9. [9]

    H. Hong, A. Ovchinnikov, G. Pogudin, and C. Yap. SIAN: software for structural identifiability analysis of ODE models.Bioinformatics, 35(16): 2873–2874, 2019. URLhttps://doi.org/10.1093/bioinformatics/ bty1069

    work page doi:10.1093/bioinformatics/ 2019

  10. [10]

    H. Hong, A. Ovchinnikov, G. Pogudin, and C. Yap. Global identifiability of differential models.Communications on Pure and Applied Mathematics, 73 (9):1831–1879, 2020. URLhttps://doi.org/10.1002/cpa.21921

    work page doi:10.1002/cpa.21921 2020

  11. [11]

    Ilmer, A

    I. Ilmer, A. Ovchinnikov, and G. Pogudin. Web-based Structural Identifiabil- ity Analyzer. InComputational Methods in Systems Biology, pages 254–265

  12. [12]

    URLhttps://doi.org/10.1007/978-3-030-85633-5_17

    work page doi:10.1007/978-3-030-85633-5_17

  13. [13]

    Ilmer, A

    I. Ilmer, A. Ovchinnikov, G. Pogudin, and P. Soto. More efficient identifia- bility verification in ODE models by reducing non-identifiability. 2022. URL https://arxiv.org/pdf/2204.01623.pdf

    work page arXiv 2022

  14. [14]

    Marker.Model theory: An introduction

    D. Marker.Model theory: An introduction. Springer, New York, 2002. URL https://doi.org/10.1007/b98860

    work page doi:10.1007/b98860 2002

  15. [15]

    Meshkat, C

    N. Meshkat, C. Kuo, and J. DiStefano. On finding and using identifiable parameter combinations in nonlinear dynamic systems biology models and COMBOS: A novel web implementation.PLoS ONE, 9(10):e110261, 2014. URLhttps://doi.org/10.1371/journal.pone.0110261

    work page doi:10.1371/journal.pone.0110261 2014

  16. [16]

    Meshkat, S

    N. Meshkat, S. Sullivant, and M. Eisenberg. Identifiability results for several classes of linear compartment models.Bulletin of Mathemati- cal Biology, 77:1620–1651, 2015. URLhttps://doi.org/10.1007/ s11538-015-0098-0

    2015

  17. [17]

    J. S. Milne. Fields and Galois theory (v5.10), 2022. URLhttps://www. jmilne.org/math/CourseNotes/ft.html

    2022

  18. [18]

    Ovchinnikov, A

    A. Ovchinnikov, A. Pillay, G. Pogudin, and T. Scanlon. Computing all iden- tifiable functions of parameters for ODE models.Systems & Control Letters, 157:105030, 2021. URLhttps://doi.org/10.1016/j.sysconle.2021. 105030

    work page doi:10.1016/j.sysconle.2021 2021

  19. [19]

    Ovchinnikov, G

    A. Ovchinnikov, G. Pogudin, and P. Thompson. Input-output equations and identifiability of linear ODE models.IEEE Transactions on Automatic Con- 18 trol, 68(2):812–824, 2023. URLhttps://doi.org/10.1109/TAC.2022. 3145571

    work page doi:10.1109/tac.2022 2023

  20. [20]

    Ovchinnikov, G

    A. Ovchinnikov, G. Pogudin, and P. Thompson. Parameter identifiability and input-output equations.Applicable Algebra in Engineering, Communica- tion and Computing, 34:165–182, 2023. URLhttps://doi.org/10.1007/ s00200-021-00486-8

    2023

  21. [21]

    Rogers.Theory of recursive functions and effective computability

    H. Rogers.Theory of recursive functions and effective computability. MIT Press, Cambridge, MA, USA, 1987. ISBN 0262680521

    1987

  22. [22]

    Sedoglavic

    A. Sedoglavic. A probabilistic algorithm to test local algebraic observability in polynomial time.Journal of Symbolic Computation, 33(5):735–755, May

  23. [23]

    URLhttps://doi.org/10.1006/jsco.2002.0532. 19

    work page doi:10.1006/jsco.2002.0532 2002